0/1背包与完全背包
背包问题的描述:
有N件物品和一个最多能被重量为W 的背包。第i件物品的重量是weight[i],得到的价值是value[i] 。每件物品只能用一次,求解将哪些物品装入背包里物品价值总和最大。
第i件物品假设为:nums[i]。
这是最基础的0/1背包问题
求解方法:
状态假设:设dp[i][j]表示前i件物品在重量为j的背包中的最大价值
状态转移方差:
不选第i件物品:
dp[i][j] = dp[i - 1][j].
选第i件物品:
dp[i][j] = dp[i - 1][j - weight[i]] + value[i]
dp[i][j] = max(dp[i - 1][j],dp[i - 1][j - weight[i]] + value[i])
代码:
for(int i = 0; i < weight.length; i++) { // 遍历物品
for(int j = 0; j <= bagWeight; j++) { // 遍历背包容量
if (j < weight[i]) 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]);
}
}
优化:将二维dp转成一维dp
代码:
for(int i = 0;i < nums.length;i++){
for(int j = bagWeight;j >= nums[i];j--){
dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);
}
}
为什么可以这样子呢,而且为什么要逆序呢?
在第i - 1层时要更新到第i层时,dp[j]与上一层的dp[j]和dp[j - x]有关。
因此在更新dp[j]的时候需要保证dp[j - x]还没有更新,因此需要进行逆序更新。
完全背包问题
完全背包与0/1背包的区别就是:完全背包选择的第i件物品可以是重复选择的,但是0/1背包每件物品只能选择一次。
完全背包中的状态转移方程变成:
dp[i][j] = max(dp[i - 1][j],dp[i][j - weight[i]] + value[i])
与0/1背包的区别在于
选择第i件物品时完全背包是: dp[i][j - weight[i]] + value[i]
0/1背包是dp[i - 1][j - weight[i]] + value[i]
因为完全背包可以重复选,因此在当前层选择第i件物品时,该物品可以在以前被选择过的。
代码为:
for(int i = 0;i < nums.length;i++){
for(int j = nums[i];j <= bagWeight;j++){
dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);
}
}
这个时候就变成了正序更新:
因为dp[j - x]需要先从第i - 1层更新到第 i 层,因此需要正序更新。
完全背包问题还有两类不同的问题:
组合和排列。
组合不考虑顺序,但是排列需要考虑
也就是说在组合问题中[1,5]和[5,1]是一种,但是在排列问题中这是两种。
这两种问题对应leetcode518和377
先上代码:
组合:
for(int x:nums){
for(int i = x;i <= target;i++){
dp[i] += dp[i - x];
}
}
排列:
for(int i = 0;i <= target;i++){
for(int x : nums){
if(i - x >= 0) dp[i] += dp[i - x];
}
}
组合问题的外层循环是物品,内层循环是重量
排列问题的外层循环是重量,内层循环是物品。
我是这么理解的,外层循环是物品,那么在计算dp[i][j]时物品顺序是定下来的。
而如果把物品放在内层循环那么就成为了计算目标j时用上了所有物品,物品顺序不定。
有点绕,这个还是需要好好理解。