1.01背包
有 N 件物品和一个容量为 V 的背包。第 i 件物品的费用是 c[i]，价值是 w[i]。
求解将哪些物品装入背包可使价值总和最大
这是最基础的背包问题，特点是：每种物品仅有一件，可以选择放或不放。
用子问题定义状态：即 f[i][v]表示前 i 件物品恰放入一个容量为 v 的背包可以
获得的最大价值。则其状态转移方程便是：
f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]}
这个方程非常重要，几乎所有跟背包相关的问题的方程都是由它衍生出来的，所以必须详细解释一下这个方程：
“将前 i 件物品放入容量为 v 的背包中”这个子问题，若只考虑第 i 件物品的策略（放或不放），那么就可以转化为一个只牵扯 前 i-1 件物品的问题。如果不放第 i 件物品，那么问题就转化为“前 i-1 件物品 放入容量为 v 的背包中”，价值为 f[i-1][v]；如果放第 i 件物品，那么问题就 转化为“前 i-1 件物品放入剩下的容量为 v-c[i]的背包中”，此时能获得的最大价值就是 f[i-1][v-c[i]]再加上通过放入第 i 件物品获得的价值 w[i]。
以上方法的时间和空间复杂度均为 O(N*V)，其中时间复杂度基本已经不能再优
化了，但空间复杂度却可以优化到 O(V)。
先考虑上面讲的基本思路如何实现，肯定是有一个主循环 i=1..N，每次算出来
二维数组 f[i][0..V]的所有值。那么，如果只用一个数组 f[0..V]，能不能保证
第 i 次循环结束后 f[v]中表示的就是我们定义的状态 f[i][v]呢？f[i][v]是由
f[i-1][v]和 f[i-1][v-c[i]]两个子问题递推而来，能否保证在推 f[i][v]时（也
即在第 i 次主循环中推 f[v]时）能够得到 f[i-1][v]和 f[i-1][v-c[i]]的值呢？
事实上，这要求在每次主循环中我们以 v=V..0 的顺序推 f[v]，这样才能保证推
f[v]时 f[v-c[i]]保存的是状态 f[i-1][v-c[i]]的值。代码如下：
cin >> n >> m;
for(int i = 1; i <= n; ++i){
cin >> value >> weigth;
for(int j = m; j >= 0; --j)
if(j >= weigth)
f[j] = max(f[j], f[j - weigth] + value);
}
那么为什么要逆序呢？在做完第i -1次循环后，此时f[][]数组中储存的是 f[i - 1][j = 0,…V]的所有的值，由于我们转移的是f[i - 1][j - w[i]]，不会更改前面的值，所有倒序可以使得前面都是f[i -1][]的值，这样就可以压缩空间了。如果还是不理解，最近刚好看到这样一个比喻： 假如你去抢劫金店，顺序就相当于我只拿一个小包装了性价比最高的东西，后来我又有了一个大包，然后我就YY我的大包体积相当于5个小包体积，所以我们能抢到5个小包里面的东西，但是01背包中的每一个东西只有一个，没那么多性价比高的东西让你抢啊。 这样想来01背包的逆序也好理解了。
那么下面就来道01背包的题练练手吧
Bone Collector
给出每种骨头的价值和大小，再给出背包的大小，要求把骨头装进背包所得的最大价值的方法。
Input
The first line contain a integer T , the number of cases.
Followed by T cases , each case three lines , the first line contain two integer N , V, (N <= 1000 , V <= 1000 )representing the number of bones and the volume of his bag. And the second line contain N integers representing the value of each bone. The third line contain N integers representing the volume of each bone.
Output
One integer per line representing the maximum of the total value (this number will be less than 231).
Sample Input
1
5 10
1 2 3 4 5
5 4 3 2 1
Sample Output
14
#include<bits/stdc++.h>
using namespace std;
int main()
{
int tt; cin >> tt;
int f[1010],v[1010],w[1010];
while (tt--) {
int N, V; cin >> N >> V;
memset(f, 0, sizeof(f));
memset(v, 0, sizeof(v));
memset(w, 0, sizeof(w));
for (int i = 1; i <= N; ++i) cin >> v[i];
for (int i = 1; i <= N; ++i) cin >> w[i];
for (int i = 1; i <= N; ++i) {
for (int j = V; j >= w[i]; --j) {
f[j] = max(f[j], f[j - w[i]] + v[i]);
}
}
cout << f[V] << endl;
}
return 0;
}
初始化的细节问题
我们看到的求最优解的背包问题题目中，事实上有两种不太相同的问法。有的题
目要求“恰好装满背包”时的最优解，有的题目则并没有要求必须把背包装满。
一种区别这两种问法的实现方法是在初始化的时候有所不同。
如果是第一种问法，要求恰好装满背包，那么在初始化时除了 f[0]为 0 其它
f[1..V]均设为-∞，这样就可以保证最终得到的 f[N]是一种恰好装满背包的最
优解。
如果并没有要求必须把背包装满，而是只希望价格尽量大，初始化时应该将
f[0..V]全部设为 0。
为什么呢？可以这样理解：初始化的 f 数组事实上就是在没有任何物品可以放入
背包时的合法状态。如果要求背包恰好装满，那么此时只有容量为 0 的背包可能
被价值为 0 的 nothing“恰好装满”，其它容量的背包均没有合法的解，属于未
定义的状态，它们的值就都应该是-∞了。如果背包并非必须被装满，那么任何
容量的背包都有一个合法解“什么都不装”，这个解的价值为 0，所以初始时状
态的值也就全部为 0 了。这个小技巧完全可以推广到其它类型的背包问题
2.完全背包
有 N 种物品和一个容量为 V 的背包，每种物品都有无限件可用。第 i 种物品的费
用是 c[i]，价值是 w[i]。求解将哪些物品装入背包可使这些物品的费用总和不
超过背包容量，且价值总和最大。
基本思路
这个问题非常类似于 01 背包问题，所不同的是每种物品有无限件。也就是从每
种物品的角度考虑，与它相关的策略已并非取或不取两种，而是有取 0 件、取 1
件、取 2 件等很多种。如果仍然按照解 01 背包时的思路，令 f[i][v]表示
前 i 种物品恰放入一个容量为 v 的背包的最大权值。仍然可以按照每种物品不同
的策略写出状态转移方程，像这样：
f[i][v]=max{f[i-1][v-k*c[i]]+k*w[i]|0<=k*c[i]<=v}
这跟 01 背包问题一样有 O(N*V)个状态需要求解，但求解每个状态的时间已经不
是常数了，求解状态 f[i][v]的时间是 O(v/c[i])，总的复杂度是超过 O(VN)的。
将 01 背包问题的基本思路加以改进，得到了这样一个清晰的方法。这说明 01
背包问题的方程的确是很重要，可以推及其它类型的背包问题。但我们还是试图
改进这个复杂度。
一个简单有效的优化
完全背包问题有一个很简单有效的优化，是这样的：若两件物品 i、j 满足
c[i]<=c[j]且 w[i]>=w[j]，则将物品 j 去掉，不用考虑。这个优化的正确性显
然：任何情况下都可将价值小费用高得 j 换成物美价廉的 i，得到至少不会更差
的方案。对于随机生成的数据，这个方法往往会大大减少物品的件数，从而加快
速度。然而这个并不能改善最坏情况的复杂度，因为有可能特别设计的数据可以
一件物品也去不掉。
这个优化可以简单的 O(N^2)地实现，一般都可以承受。另外，针对背包问题而
言，比较不错的一种方法是：首先将费用大于 V 的物品去掉，然后使用类似计数
排序的做法，计算出费用相同的物品中价值最高的是哪个，可以 O(V+N)地完成
这个优化。
转化为 01 背包问题求解
既然 01 背包问题是最基本的背包问题，那么我们可以考虑把完全背包问题转化
为 01 背包问题来解。最简单的想法是，考虑到第 i 种物品最多选 V/c[i]件，于
是可以把第 i 种物品转化为 V/c[i]件费用及价值均不变的物品，然后求解这个
01 背包问题。这样完全没有改进基本思路的时间复杂度，但这毕竟给了我们将
完全背包问题转化为 01 背包问题的思路：将一种物品拆成多件物品。
更高效的转化方法是：把第 i 种物品拆成费用为 c[i]*2^k、价值为 w[i]*2^k 的
若干件物品，其中 k 满足 c[i]*2^k<=V。这是二进制的思想，因为不管最优策略
选几件第 i 种物品，总可以表示成若干个 2^k 件物品的和。这样把每种物品拆成
O(log(V/c[i]))件物品，是一个很大的改进。但我们有更优的 O(VN)的算法。
O(VN)的算法
这个算法使用一维数组，先看伪代码：
for i=1..N
for v=0..V
f[v]=max{f[v],f[v-cost]+weight}
你会发现，这个伪代码与01背包的伪代码只有 v 的循环次序不同而已。为什么这样
一改就可行呢？首先想想为什么 01背包 中要按照 v=V..0 的逆序来循环。这是因为
要保证第 i 次循环中的状态 f[i][v]是由状态 f[i-1][v-c[i]]递推而来。换句话
说，这正是为了保证每件物品只选一次，保证在考虑“选入第 i 件物品”这件策
略时，依据的是一个绝无已经选入第 i 件物品的子结果 f[i-1][v-c[i]]。而现
在完全背包的特点恰是每种物品可选无限件，所以在考虑“加选一件第 i 种物
品”这种策略时，却正需要一个可能已选入第 i 种物品的子结果 f[i][v-c[i]]，
所以就可以并且必须采用 v=0..V 的顺序循环。这就是这个简单的程序为何成立
的道理。
这个算法也可以以另外的思路得出。例如，基本思路中的状态转移方程可以等价
地变形成这种形式：
f[i][v]=max{f[i-1][v],f[i][v-c[i]]+w[i]}
将这个方程用一维数组实现，便得到了上面的伪代码。
例题
B - Piggy-Bank
#include<bits/stdc++.h>
using namespace std;
const int maxn = 50000;
int dp[maxn], w[maxn], v[maxn];
int e, f, tt, n;
int main()
{
cin >> tt;
while (tt--) {
memset(dp, 0x3f, sizeof(dp));
dp[0] = 0;
cin >> e >> f >> n;
for (int i = 0; i < n; ++i) cin >> v[i] >> w[i];
for (int i = 0; i < n; ++i) {
for (int j = 1; j <= f - e; ++j) {
if (j >= w[i])
dp[j] = min(dp[j], dp[j - w[i]] + v[i]);
}
}
if (dp[f - e] != 0x3f3f3f3f)
cout<<"The minimum amount of money in the piggy-bank is "<<dp[f-e]<<"."<<endl;
else
cout<<"This is impossible."<<endl;
}
return 0;
}
