vector<vector<int>> dp(weight.size(), vector<int>(bagweight + 1, 0));
for (int j = weight[0]; j <= bagweight; j++)
{
dp[0][j] = value[0];
}
// weight数组的大小 就是物品个数
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]);
}
}vector<int> dp(bagWeight + 1, 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分割等和子集
class Solution {
public:
bool canPartition(vector<int>& nums)
{
int sum=0;
for(auto a:nums) sum+=a;
if(sum%2!=0) return false;
sum/=2;
vector<int>dp(sum+1,0);
for(int i=0;i<nums.size();i++)
{
for(int j=sum;j>=nums[i];j--)
{
dp[j]=max(dp[j],dp[j-nums[i]]+nums[i]);
}
}
if(dp[sum]==sum) return true;
return false;
}
};文章来源地址https://www.toymoban.com/news/detail-646215.html
文章来源：https://www.toymoban.com/news/detail-646215.html
到了这里，关于代码随想录day42（背包）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
