讨论/《零起步学算法》 - 方法:动态规划/
《零起步学算法》 - 方法:动态规划
共 2 个回复

这里我贴一下C++的代码,供交流学习。

class Solution {
public:
    int backpackComplete(int W, vector<int>& weights, vector<int>& values) {
        /*使用最原始的二维数组进行动态规划计算*/
        if (W <= 0 || weights.empty() || values.empty()) return 0;
        // 状态空间。dp[i][j]表示背包容量为j时,对于第i个物品的最大价值
        vector<vector<int>> dp(weights.size()+1, vector<int>(W + 1, 0));
        // 状态空间转移。先逐物品遍历,再逐背包容量遍历,最后逐重复装入i物品遍历
        for (int i = 1; i <= weights.size(); i++) {
            for (int j = 1; j <= W; j++) {
                for (int k = 0; k*weights[i-1] <= j; k++) {
                    dp[i][j] = max(dp[i][j], dp[i - 1][j - k*weights[i - 1]] + k*values[i - 1]);
                }
            }
        }
        // 返回值,最后一个值
        return dp.back().back();
    }
};
1

谢谢你哟,我也学习一下。