乐趣区

关于背包问题:01背包和完全背包的理解

jiezi

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…
这个视频是我找到讲背包十分细的一位老师，大家能够反复观看，认真琢磨。

退出移动版