1. 背包问题
题目：有一个容量为 V 的背包，和一些物品。这些物品分别有两个属性，体积 w 和价值 v，每种物品只有一个。要求用这个背包装下价值尽可能多的物品，求该最大价值，背包可以不被装满。
例子
背包最大容量：50
物品重量为：{10,20,30,40,60}
物品价值为：{1,3,5,7,9}
输出：8
解释：当选择物品重量为20，30或者10，40对应的价值最大。
0-1 背包问题中，物品只有两种状态，装载或者不装载，因此被称为0-1背包。除此之外还有完全背包和多重背包。
- 找子问题，第一，包的当前容量比物品小，装不下，这时的最大价值和前个物品的最大价值是一样的。我们令表示前个物品在背包容量为所能达到的最大价值。第二，包的当前可用容量比物品大，这个时候要决定是否添加下一个物品，因为在体积相同的情况下，总价值不一定更大。
- 找到状态转移方程，我们用辅助函数表示当前物品的总重量。
-
确定边界条件：
，不装物品时最大价值为0.，同理，即背包容量为0时，最大价值也为0.
时间复杂度：，状态数量为V*N, V为背包容量，N为物品数目，状态转移复杂度为。
空间复杂度：, 为dp数组大小。
变式：要求完全装满背包。
我们令，不装物品时最大价值为0.，，这样的话，在刚好大于0.
优化：用一维数组表示
因为dp的物品数量维度i，仅与前一项有关，因此可以优化。为保证每个物品只能使用一次，我们倒序遍历所有的值 注意后面的dp[j]其实是上一次的结果，这相当于滚动数组。优化后空间复杂度为。
int backpack(int V, vector<int>val, vector<int> weight)
{//V为背包最大容量，val为物品价值数组，weig为物品重量数组
int N = val.size();
vector<int> dp(V+1); //dp[j]表示容量为j的最大价值
dp[0] = 0;
for(int i = 1; i <= V;i++) dp[i] = 0;
for(int i = 1; i <= N ;i++)
{
for(int j = V; j >= weight[i-1];j--)
dp[j] = max(dp[j],dp[j-weight[i-1]]+val[i-1]);
}
return dp[V];
}
完全背包问题
我们让每种物品数量可以无限，。
例子
背包最大容量：60
物品重量为：{10,20,30,40,60}
物品价值为：{1,2,5,7,8}
输出：10
解释：当选择物品重量为两个30对应的价值最大。
我们将上述优化算法由倒序遍历J变为正序遍历J即可实现。
int backpack(int V, vector<int>val, vector<int> weight)
{//V为背包最大容量，val为物品价值数组，weig为物品重量数组
int N = val.size();
vector<int> dp(V+1); //dp[j]表示容量为j的最大价值
dp[0] = 0;
for(int i = 1; i <= V;i++) dp[i] = 0;
for(int i = 1; i <= N ;i++)
for(int j = weight[i-1]; j <= V;j++)
if(dp[j-weight[i-1]]+val[i-1]>dp[j])
dp[j] = dp[j-weight[i-1]]+val[i-1];
return dp[V];
}
多重背包问题
多重背包问题介于0-1背包和完全背包之间。
我们除了给出背包的最大容量，物品的重量和价值，还给出物品的最大数量k。
我们可以将多重背包问题转化为0-1背包，即将每种物品视为k种不同的物品，这样的时间复杂度为，由此可见，降低每件物品的数量可以大大降低其时间复杂度。我们运用一些tricky技巧，将原来数量为k的物品拆分为若干组，每组物品看成一件物品，其价值和重量为该组所有物品之和。.得到新的时间复杂度为。
例题 p1757通天之分组背包
题目描述
自 0101 背包问世之后，小 A 对此深感兴趣。一天，小 A 去远游，却发现他的背包不同于 0101 背包，他的物品大致可分为 kk 组，每组中的物品相互冲突，现在，他想知道最大的利用价值是多少。
输入格式
两个数 m,nm,n，表示一共有 nn 件物品，总重量为 mm。
接下来 nn 行，每行 33 个数 a_i,b_i,c_iai*,*bi,c**i，表示物品的重量，利用价值，所属组数。
输出格式
一个数，最大的利用价值。
