0-1背包问题：
有n个物品，价值为v，重量为w，装进容量为c的背包中，问怎么装使得背包价值最大。
算法思想：动态规划
dp[i][j] 表示从0-i个物品中选择加入容量为j的背包中获取的最大价值
公式：
dp[i][j] = max(dp[i-1][j] , dp[i-1][j-weight[i]] + value[i])
第i个物品不选：
dp[i-1][j]
第i个物品选择：
dp[i-1][j-weight[i]] + value[i] ， 即0-i-1 个物品，放进容量为j-weight[i]时，获取的最大价值，再加上i的价值。
初始化：
第一行初始化：
加入i表示物品，j表示背包容量。第一行初始化为把物品0放入背包为0-j的背包中的最大价值
第一列初始化：
容量为0的背包最大价值，因此初始哈为0
int beibao01 (vector<int> value, vector<int> weight, int c)
{
vector<vector<int>> dp(value.size(), vector<int> (c+1, 0));
for(int i=0;i<value.size();i++)
{
dp[i][0] = 0;
}
for(int j=0;j<=c;j++)
{
if(value[0]< c) dp[0][j] = value[0];
else dp[0][j] = 0;
}
for(int i = 1;i<value.size();i++)
{
for(int j=1;j<=c;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[j] = max(dp[j], dp[j-weight[i]] + value[i])
算法思想：相当于是0-1背包问题，物品价值为nums[i],重量为nums[i],装到容量为 sum/2的背包中
使用0-1背包的思想。
class Solution {
public:
bool canPartition(vector<int>& nums) {
//相当于是0-1背包问题，物品价值为nums[i],重量为nums[i],装到容量为 sum/2的背包中
int sum = 0;
for(int i=0;i<nums.size();i++)
{
sum = sum + nums[i];
}
if(sum%2==1)
return false;
sum = 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;
}
};
二维数组的实现方法：
class Solution {
public:
bool canPartition(vector<int>& nums) {
//相当于是0-1背包问题，物品价值为nums[i],重量为nums[i],装到容量为 sum/2的背包中
int sum = 0;
for(int i=0;i<nums.size();i++)
{
sum = sum + nums[i];
}
if(sum%2==1)
return false;
sum = sum/2;
vector<vector<int>> dp(nums.size(), vector<int> (sum+1, 0));
//初始化
for(int i=0;i<nums.size();i++) //容量为0的背包放的最大价值是0
{
dp[i][0] = 0;
}
for(int j=0;j<=sum;j++)
{
if(j<nums[0]) //太小了放不下
dp[0][j] = 0;
else
dp[0][j] = nums[0];
}
for(int i=1;i<nums.size();i++) //遍历物品
{
for(int j=1;j<=sum;j++) //遍历背包
{
if(j<nums[i])
dp[i][j] = dp[i-1][j];
else
dp[i][j] = max(dp[i-1][j], dp[i-1][j-nums[i]]+ nums[i]);
}
if(dp[i][sum]==sum)
return true;
}
return false;
}
};
