三种写法省了多少

👁️ 1 人浏览 💬 0 人评论 ❤️ 添加收藏

暴力和填表已给出，补全记忆化。输出三样：暴力调用次数/记忆化调用次数/三个答案是否全相同（相同输出结果一致，否则结果不一致）。

（本题用 g++ -std=c++17 -O0 编译。）

提交你的答案

请登录后提交答案。

去登录

← 第三步把递归换成填表设计状态先问自己什么（C++） →

更多题目

代码编辑器

语言： Ctrl + Enter 运行

#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
using namespace std;
using Item = pair<int, int>;   // (重量, 价值)

const vector<Item> ITEMS = {{3, 8}, {4, 9}, {5, 11}};

const vector<Item> IT = {{1, 1}, {2, 3}, {1, 2}, {2, 2}, {1, 1}, {2, 4}, {1, 3}, {2, 2}, {1, 1}, {2, 3}};
long long calls = 0;

int go_rec(int i, int c) {
    calls++;
    if (i == (int)IT.size()) return 0;
    auto [w, v] = IT[i];
    int best = go_rec(i + 1, c);
    if (c >= w) {
        int take = go_rec(i + 1, c - w) + v;
        if (take > best) best = take;
    }
    return best;
}

vector<vector<int>> memo;

int go_memo(int i, int c) {
    calls++;
    // TODO: memo[i][c] 不是 -1 就直接返回它
    // TODO: i 到头返回 0；否则照常两条路取大的（「拿」那一支只调用一次）
    // TODO: 存进 memo[i][c] 再返回
    (void)i; (void)c;
    return 0;
}

vector<long long> knap1d(const vector<Item>& items, int cap) {
    vector<long long> dp(cap + 1, 0);
    for (auto [w, v] : items) {
        for (int c = cap; c >= w; c--) {
            if (dp[c - w] + v > dp[c]) dp[c] = dp[c - w] + v;
        }
    }
    return dp;
}

int main() {
    calls = 0;
    int a = go_rec(0, 8);
    long long na = calls;
    calls = 0;
    memo.assign(IT.size() + 1, vector<int>(9, -1));
    int b = go_memo(0, 8);
    long long nb = calls;
    long long c = knap1d(IT, 8)[8];
    cout << na << "/" << nb << "/" << (a == b && b == c ? "结果一致" : "结果不一致") << endl;
}

本次输入：

输出：

👩‍🏫

💬 题目评论

三种写法省了多少

更多题目

全部评论