文章链接:背包问题-二维dp
所谓背包问题,最基础的是01背包,前提是背包容量有限,每个物品有自己的价值和重量,放/不放 就组成了问题的 0/1
对于背包问题,有一种写法, 是使用二维数组,即dp[i][j]
表示从下标为[0-i]
的物品里任意取,放进容量为j
的背包,价值总和最大是多少
递推公式方面,可以通过两个情况来得到dp[i][j]
:
dp[i - 1][j]
推出,即背包容量为j
,里面不放物品i的最大价值,此时dp[i][j]
就是dp[i - 1][j]
。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得到的最大价值写出来代码就是:
for(int i = 1; i < weight.size(); i++) { // 遍历物品for(int j = 0; j <= bagweight; j++) { // 遍历背包容量if (j < weight[i]) dp[i][j] = dp[i - 1][j];else dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);}
}
文章链接:背包问题-一维dp
为了背包问题特意开个二维数组,有点浪费空间,那么就缩为一维数组dp[j],更新的时候原地覆盖就可以了
dp[j]表示容量为j的背包能够装下的最高价值,
递推公式:dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
遍历时顺序严格不可交换,因为物品i来了之后,要用到物品i-1的结果,所以有两大原则:
dp[j]
写出来代码就是
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]); }
}
题目链接:Leetcode416. 分割等和子集
一个商品如果可以重复多次放入是完全背包,而只能放入一次是01背包,写法还是不一样的。要明确本题中我们要使用的是01背包,因为元素我们只能用一次。
这个用背包来做还是挺有难度的
class Solution {
public:bool canPartition(vector& nums) {vector dp(10001,0);int sum=0,target=0;for(int i=0;isum+=nums[i];}if(sum%2==1) return false;target=sum/2;for(int i=0;ifor(int j=target;j>=nums[i];j--){dp[j]=max(dp[j],dp[j-nums[i]]+nums[i]);}}return dp[target]==target;}
};