01背包和完全背包的理解

1. 01背包

01背包是所有复杂背包的基础，掌握了对后面更复杂的背包理解有很大的帮助；
背包问题物品只能拿和不拿，最多拿一次，用来动态规划的方法，先上结论：
动态规划方程式:
参数说明：

dp是指背包最大价值
j指最大背包容量
i指的是当前正在放入背包的第i件物品，
w[i]指当前放入物品的重量
v[i]指当前放入物品的价值。

dp[j]=max(dp[j], dp[j-w[i]]+v[i])

下面是计算程序，可以得到一张动态规划表，根据不同物品数量、不同背包容量获得不同的结果

let m = 10 //背包容量
let n = 4 //物品数量
const w = [0, 3, 4, 5, 6] //物品重量
const v = [0, 3, 5, 3, 8] //物品价值

//dp数组，结果存放的不同背包容量的最大价值
const dp = []

// 按顺序放入物品
for (i = 1;i <= n;i++) {
    // 不同背包容量，倒叙，因为数组左边的值是上一条数据最为条件，计算出当条的结果存放在右边，最后更新整个数组
    for (j = m;j >= 1; j--) {
        if (j >= w[i])
            dp[j] = max(dp[j], dp[j-w[i]] + v[i])
    }

    for (k = 1; k <= m; k++) {
        console.log(dp[k])
    }
}

2. 完全背包

完全背包唯一不同就是，物品可以无限次放进背包，其他条件和01背包一样，结果如下：

let m = 10 //背包容量
let n = 4 //物品数量
const w = [0, 3, 4, 5, 6] //物品重量
const v = [0, 3, 5, 3, 8] //物品价值

//dp数组，结果存放的不同背包容量的最大价值
const dp = []

// 按顺序放入物品
for (i = 1;i <= n;i++) {
    // 不同背包容量，正序，因为数组左边的值是上一条数据最为条件，计算出当条的结果存放在右边，最后更新整个数组
    for (j = 1;j <= m; j++) {
        if (j >= w[i])
            dp[j] = max(dp[j], dp[j-w[i]] + v[i])
    }

    for (k = 1; k <= m; k++) {
        console.log(dp[k])
    }
}

发现了么，唯一的不同就是背包变成了正序，其他地方都一样，为什么呢？
总结：
01背包总是用上一个物品状态获取下一个物品状态，所以用数组左边的数据去计算，因为左边的数据就是上一物品数据；
而完全背包，因为不限制物品放入数量，所以把当前物品再次放入即可，所有当前物品放入后结果放在左边，再次计算是左边就当成条件继续使用即可。

参考视频：https://www.bilibili.com/vide...
这个视频是我找到讲背包非常细的一位老师，大家可以重复观看，仔细揣摩。