免飞网站,wordpress取消邮件验证码,丽江最新防疫政策,网络营销企业网站推广一、二维数组
1、状态转移方程#xff1a;
不放物品i#xff1a;由dp[i - 1][j]推出#xff0c;即背包容量为j#xff0c;里面不放物品i的最大价值#xff0c;此时dp[i][j]就是dp[i - 1][j]。(其实就是当物品i的重量大于背包j的重量时#xff0c;物品i无法放进背包中
不放物品i由dp[i - 1][j]推出即背包容量为j里面不放物品i的最大价值此时dp[i][j]就是dp[i - 1][j]。(其实就是当物品i的重量大于背包j的重量时物品i无法放进背包中所以背包内的价值依然和前面相同。)放物品i由dp[i - 1][j - weight[i]]推出dp[i - 1][j - weight[i]] 为背包容量为j - weight[i]的时候不放物品i的最大价值那么dp[i - 1][j - weight[i]] value[i] 物品i的价值就是背包放物品i得到的最大价值
所以递归公式 dp[i][j] max(dp[i - 1][j], dp[i - 1][j - weight[i]] value[i]);
2、初始化
1从dp[i][j]的定义出发如果背包容量j为0的话即dp[i][0]无论是选取哪些物品背包价值总和一定为0。
2状态转移方程 dp[i][j] max(dp[i - 1][j], dp[i - 1][j - weight[i]] value[i]); 可以看出i 是由 i-1 推导出来那么i为0的时候就一定要初始化。
dp[0][j]即i为0存放编号0的物品的时候各个容量的背包所能存放的最大价值。
那么很明显当 j weight[0]的时候dp[0][j] 应该是 0因为背包容量比编号0的物品重量还小。
当j weight[0]时dp[0][j] 应该是value[0]因为背包容量放足够放编号0物品。
for (int j 0 ; j weight[0]; j) {dp[0][j] 0;
}
// 正序遍历
for (int j weight[0]; j bagweight; j) {dp[0][j] value[0];
}
3其他下标初始化 dp[i][j] max(dp[i - 1][j], dp[i - 1][j - weight[i]] value[i])
dp[1][1] max(dp[0][1], dp[0][1- weight[i]] value[i]) 一定在其左方且上方
故一定初始化过了可以设置为任何值为了方便现默认初始化为0。
二、一维滚动数组
1、一维dp数组中dp[j]表示容量为j的背包所背的物品价值可以最大为dp[j]
dp[j] max(dp[j], dp[j - weight[i]] value[i])
2、初始化
1dp[0]0因为背包容量为0所背的物品的最大价值就是0。
2假设物品价值都是大于0的为了不被初始值覆盖所以dp数组初始化的时候都初始为0
3、遍历顺序
倒序遍历
解释1列表后面的值需要通过与上一层遍历得到的前面的值比较确定
解释201背包每个背包都只有一个这个包放于不放与上一个包的状态有关而左边的数组是描述上一个包状态的量右边的数是当前包状态的一个待定代码里是右边数组的确定需要左边的数所以在计算出右边的数之前不能破坏左边的数。
解释3对于二维我每个新的dp数字的结果都来源于上面和左边其实一维也本该是这样但一维的时候如果还是从左到右那么我其实左边的数字已经更新过了左边已经不是“原来的”左边了这会造成某些重复计算即使上面还是原来的上面得到的数字也是不正确的。而如果我们在背包层里层从右到左地遍历那么左边的元素永远不会因为我前一次的操作被覆盖上新的值这样可以得到正确的值。
