01背包中二维dp数组的两个for遍历的先后循序是可以颠倒了,一维dp数组的两个for循环先后循序一定是先遍历物品i,再遍历背包容量j。
在完全背包中,对于一维dp数组来说,其实两个for循环嵌套顺序同样无所谓!
01背包
for(int i = 1; i <= weight.size(); i ++) { // 遍历物品
for(int j = bagWeight; j >= weight[i]; j --) { // 遍历背包容量
dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
}
}
完全背包
for(int i = 1; i <= weight.size(); i ++) { // 遍历物品
for(int j = weight[i]; j <= bagWeight; j ++) { // 遍历背包容量
dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
}
}
for(int j = 1; j <= bagWeight; j++) { // 遍历背包容量
for(int i = 1; i <= weight.size(); i++) { // 遍历物品
if (j - weight[i] >= 0) dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
}
}
01背包的递推公式:dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
求装满背包有几种方法,一般公式都是:dp[j] += dp[j - nums[i]];
组合不强调元素之间的顺序,排列强调元素之间的顺序
####完全背包
-如果求组合数就是外层for循环遍历物品,内层for遍历背包。
-如果求排列数就是外层for遍历背包,内层for循环遍历物品。