[Vssue]背包理论基础01背包-1.md

[youngyangyang04]

https://www.programmercarl.com/%E8%83%8C%E5%8C%85%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%8001%E8%83%8C%E5%8C%85-1.html

[DEZREMNACUI]

打卡

[liu-ruyang]

dp问题打卡了

[Du1in9]

int[][] dp = new int[weight.length][w];

for (int j = weight[0]; j <= w + 1; j++) {
    dp[0][j] = value[0];
}
for (int i = 1; i < weight.length; i++) {
    for (int j = 0; j <= w; j++) {
        if (weight[i] > j) {
            dp[i][j] = dp[i - 1][j];
        } else {
            dp[i][j] = Math.max(dp[i - 1][j],dp[i - 1][j - weight[i]] + value[i]);
        }
    }
}
return dp[weight.length - 1][w];

// 例: w = 4, weight = [1,3,4], value = [15,20,30]
i = 1:  weight[1] = 3
    j = 0: 满足 3 > 0（不放物品 1）, dp[1][0] = 0
    j = 1: 满足 3 > 1（不放物品 1）, dp[1][1] = 15（放物品 0）
    j = 2: 满足 3 > 2（不放物品 1）, dp[1][2] = 15（放物品 0）
    j = 3: 不满足 3 > 3（放物品 1）, dp[1][3] = max(15, 20) = 20（不放物品 0）
    j = 4: 不满足 3 > 4（放物品 1）, dp[1][4] = max(15, 35) = 35（放物品 0）
i = 2:  weight[2] = 4
    j = 0: 满足 4 > 0（不放物品 2）, dp[2][0] = 0
    j = 1: 满足 4 > 1（不放物品 2）, dp[2][1] = 15（放物品 0, 不放物品 1）
    j = 2: 满足 4 > 2（不放物品 2）, dp[2][2] = 15（放物品 0, 不放物品 1）
    j = 3: 满足 4 > 3（不放物品 2）, dp[2][3] = 20（不放物品 0, 放物品 1）
    j = 4: 不满足 4 > 4（放物品 2）, dp[2][4] = max(35, 30) = 35（放物品 0, 放物品 1）

[D0112]

dp[1][4] = max(dp[0][4], dp[0][1] + 物品1 的重量) “物品1 的重量”是不是应该改为“物品1 的价值”呢？

[IamXulin]

感觉很多地方语句不通

[ZYKWLJ]

@D0112

dp[1][4] = max(dp[0][4], dp[0][1] + 物品1 的重量) “物品1 的重量”是不是应该改为“物品1 的价值”呢？

就是在找你这句，你不评论我评论

[ZYKWLJ]

这个是不是只要初始化了dp[0][0]=0就行了？毕竟其他的都是从这里起源的。

[ZYKWLJ]

// 初始化： // 其实不初始化也可以的，因为这里的数组默认为0，后面自己会加上value，相当于自己遍历的时候就初始化了。 // 不过carl哥的初始化后，会让人更好理解该问题的核心要义

[ZRICHARD9527]

物品012 和123混淆，重量和价值混淆 你自己写完文章不再看一下句子通不通？？？