第二步压掉一维

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

二维版已给出，补全一维版，输出三样：一维答案/二维格子数/一维格子数。

本路线的物品：(重 3 值 8)、(重 4 值 9)、(重 5 值 11)，写成 vector<pair<int, int>>，auto [w, v] 取出重量和价值。

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

提交你的答案

请登录后提交答案。

去登录

← 第一步两种背包第三步两个区间 DP →

更多题目

代码编辑器

语言： 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}};

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

vector<long long> knap1d(const vector<Item>& items, int cap) {
    vector<long long> dp(cap + 1, 0);
    for (auto [w, v] : items) {
        // TODO: 容量 c 从 cap 倒着数到 w，用 dp[c - w] + v 更新 dp[c]
        (void)w; (void)v;
    }
    return dp;
}

int main() {
    auto d2 = knap2d(ITEMS, 10);
    auto d1 = knap1d(ITEMS, 10);
    cout << d1[10] << "/" << d2.size() * d2[0].size() << "/" << d1.size() << endl;
}

本次输入：

输出：

👩‍🏫

💬 题目评论

第二步压掉一维

更多题目

全部评论