当前位置：首页 > article >正文

代码随想录|01背包理论基础，01背包之滚动数组，416.分割等和子集

article 2025/2/27 13:07:10

01背包理论基础

文章链接：代码随想录

状态：没做出来

思路：

做动态规划的题目，最好的过程就是自己在纸上举一个例子把对应的dp数组的数值推导一下

五部曲：

①这里要定义二维数组，因为有两个维度，一个是物品一个是背包容量

dp[i][j]的含义：从下标为[0-i]的物品内任取，放进容量为j的背包，价值总和最大为多少

②递推公式：dp[i][j]可以从哪里推导出来：

a.不放物品：dp[i][j] = dp[i - 1][j]，这里也分俩种情况，一个是放不下下一个物品，一个是能放但是不放，要分别判断

b.放物品：dp[i][j] = dp[i-1][j - weight[i]] + values[i]

for(int i = 1;i < M;i++)
{
for(int j = 1;j <= N;j++)
{
if(j < spaces[i]) dp[i][j] = dp[i-1][j];
else
{
dp[i][j] = max(dp[i-1][j],dp[i-1][j - spaces[i]] + values[i]);
}
}
}

③初始化：看推导公式，dp[i][j]是从i- 1推导出来的，j也是从j前面的元素推导而来，则初始化时就将左上角元素初始化掉即可

for (int i = 1; i < weight.size(); i++) {  // 当然这一步，如果把dp数组预先初始化为0了，这一步就可以省略，但很多同学应该没有想清楚这一点。
    dp[i][0] = 0;
}
// 正序遍历
for (int j = weight[0]; j <= bagweight; j++) {
    dp[0][j] = value[0];
}

注意，这里在定义dp数组时，要将背包容量定义时加1，这样才能保证背包被正好装满这种情况是不被遗漏的，同理在初始化和遍历循环时，都要对背包的遍历带等号

④遍历顺序：先遍历物品再遍历背包即可，其实反过来也可以，习惯问题

--------------------------------------------

01背包之滚动数组

文章链接：代码随想录

思路：把i-1的数据拷贝到第i层，直接在第i层计算，就是把二维数组转化为一维数组计算

需要满足的条件是上一层可以重复利用，就可以直接拷贝到当前层

①含义：dp[j]表示容量为j的背包能装的最大价值是多少

②递推公式：类比二维的dp数组

dp[j] = max(dp[j] , dp[j - weight[i]] + value[i] )

③初始化：一维数组的初始化比较简单，直接dp[0] = 0;

④递推顺序：

这里是重点，还是两次遍历，首先要记住这里面必须先遍历物品再遍历背包，其次背包必须要倒序遍历，否则会导致一个物品被放进去两次

for(int i = 0; i < weight.size(); i++) { // 遍历物品
    for(int j = bagWeight; j >= weight[i]; j--) { // 遍历背包容量
        dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);

    }
}

416.分割等和子集

文章链接：代码随想录

状态：没做出来

思路：重点是要看穿题目的包装理解这是一个01背包问题，本题要求集合中能出现sum/2,由于本题商品是数字，他的重量和对应的价值是相同的，然后最后的判断标准是dp[ sum / 2] == sum / 2

其他的就和01背包基本一致了

初始化：dp[0] = 0;

for(int i = 1;i < nums.size();i++)

for(int j = target; j >= nums[i] ;j--)

dp[j] = max(dp[j] , dp[ j - nums[i] ] + nums[i]);

还有要注意的点是定义dp数组，vector<int> dp(10001,0);

因为每个数组的元素不会超过100，数组的大小不超过200

总和不会超过20000，初始化为10001即可。