[Vssue]背包理论基础01背包-2.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-2.html

[Du1in9]

int[] dp = new int[w + 1];

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

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