programmercarl.com

和0 - 1背包的区别是完全背包 每件物品都有无限 个。

一维dp

for (int i = 0; i < n; i ++) {
    for (int j = weight[i]; j <= capacit; j ++) { // 从倒序改为正序
        dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
		}
}

二维dp

for (int i = 0; i < n; i ++) { // 遍历物品
    for (int j = 1; j <= capacity; j ++) { // 遍历容量
        if (j < weight[i]) {
            dp[i][j] = dp[i - 1][j];
        } else {
            dp[i][j] = max(dp[i - 1][j], dp[i][j - wegiht[i]] + value[i]);
																			 //dp[i - 1]变成了dp[i]
        }
    }
}