讨论/《零起步学算法》 - 0-1 背包问题/
《零起步学算法》 - 0-1 背包问题
共 3 个回复

我贴一下C++的代码。

class Solution {
public:
    int backpack01(int W, vector<int>& weights, vector<int>& values) {
        if (W <= 0 || weights.empty() || values.empty()) return 0;
        // 状态空间,行:物品序号,列:背包剩余容量。初始为0。在上面增加一行,左侧增加一列
        vector<vector<int>> dp(weights.size() + 1, vector<int>(W + 1, 0));
        // 状态空间转移. 先逐物品遍历,再逐背包剩余容量遍历,分别计算dp[i][j]状态下的最大收益
        for (size_t i = 1; i <= weights.size(); i++)
        {
            //j从当前物品重量开始遍历即可,dp[i][j]=max(不装,装当前物品的最大收益)
            for (int j = weights[i - 1]; j <= W; j++) {
                dp[i][j] = max(dp[i - 1][j], values[i - 1] + dp[i - 1][j - weights[i - 1]]);
            }
        }
        return dp.back().back();
    }
};
2

威哥,你那个递归树的右子树我没明白,(1,1)下面为什么是(2,2)呀,(1,1)是选中了第一个物品,(2,2)是不选第一个物品,选第二个物品。既然是递归树,那么(1,1)的子节点都得要选第一个物品呀,为啥(2,2)却没选第一个物品呀?

1

不好意思,我写错了,(1, 1) 下面是 (2, 1),我找人改一下。我重新画了一张图,点击查看。欢迎交流,假期愉快!