A - Proud Merchants HDU - 3466（带限制的01背包）
题意： 给你m元，去买大米，每袋大米给你p，q，v 当你手中的钱 >= q时，才能买价格为p的这袋大米，它的价值是v，求最大价值。
01背包的转移方程根据题意很容易写出来，但是会有问题。
for (int i = 1; i <= n; ++i)
for (int j = m; j >= q[i]; --j)
dp[j] = max(dp[j], dp[j - p[i]] + v[i]);
考虑到了可能存在排序的问题，就按 q < 排序了，过样例，但是WA了。如果买同样的东西，肯定先买q[i]大的，才能保证还能有再买东西的可能。如何让买的东西多上加多呢，还需要买p[i]便宜的，那手中的钱减小的速度就变慢了，这样也能保证还能存在继续买东西的可能。所以最优策略应该是先买q[i] - p[i]最大的。又因为状态转移方程是逆序更新的，所以按q[i] - p[i] < 排序。
1 #include <cstdio>View Code
2 #include <algorithm>
3 #include <cstring>
4 using namespace std;
5 const int N = 500 + 5;
6 const int M = 5000 + 5;
7
8 int n, m, dp[M];
9
10 struct node {
11 int p, q, v;
12 } a[N];
13
14 bool cmp(node a, node b) {
15 return a.q - a.p < b.q - b.p; // 关键点
16 }
17
18 int main() {
19 while (~scanf("%d%d", &n, &m)) {
20 memset(dp, 0, sizeof(dp));
21 for (int i = 1; i <= n; ++i)
22 scanf("%d%d%d", &a[i].p, &a[i].q, &a[i].v);
23 sort(a + 1, a + n + 1, cmp);
24 for (int i = 1; i <= n; ++i)
25 for (int j = m; j >= a[i].q; --j)
26 dp[j] = max(dp[j], dp[j - a[i].p] + a[i].v);
27 // for (int i = 1; i <= m; ++i)
28 // printf("dp[%d]=%d%s", i, dp[i], i == m ? "\n" : " ");
29 printf("%d\n", dp[m]);
30 }
31 return 0;
32 }
C - Piggy-Bank HDU - 1114（带限制的完全背包）
题意：给出n个硬币的价值和体积，问你能否正好装满背包，若能装满，求总价值的最小值
一般背包要求求最小值，这里初始化为INF，然后用一维的完全背包的方法直接更新就行
1 #include <cstdio>View Code
2 #include <cstring>
3 #include <algorithm>
4 using namespace std;
5 const int INF = 0x3f3f3f3f;
6 const int N = 500 + 5;
7 const int M = 1e4 + 5;
8
9 int E, F, n;
10 int dp[M], p[N], w[N];
11
12 int main() {
13 int T; scanf("%d", &T);
14 while (T--) {
15 scanf("%d%d%d", &E, &F, &n);
16 for (int i = 1; i <= n; ++i)
17 scanf("%d%d", &p[i], &w[i]);
18 memset(dp, INF, sizeof(dp));
19 dp[0] = 0;
20 for (int i = 1; i <= n; ++i)
21 for (int j = w[i]; j <= F - E; ++j)
22 dp[j] = min(dp[j], dp[j - w[i]] + p[i]);
23 if (dp[F - E] != INF)
24 printf("The minimum amount of money in the piggy-bank is %d.\n", dp[F - E]);
25 else
26 printf("This is impossible.\n");
27 }
28 return 0;
29 }
D - I love sneakers! HDU - 3033（分组背包变形）
背包九讲中的分组背包，是每组中最多买一件，而这道题是每组中至少买一件
背包九讲给出的分组背包伪代码，其实就是分组的01背包。
但是这道题，需要对当前情况进行判断是否合法，必须由合法的情况更新过去。
我们考虑两种情况，当前物品是否是本组中第一次被选的，是第一次，就可以由上一组更新这一组
不是第一次，就可以组内更新，相当于组内的01背包。
还要注意初始化的问题，需要将所有不和法的情况置为-1
1 #include <cstdio>View Code
2 #include <cstring>
3 #include <algorithm>
4 #include <vector>
5 using namespace std;
6 const int M = 1e4 + 5;
7
8 int dp[15][M], n, m, k;
9 vector < pair<int, int> > vec[15];
10
11 int main() {
12 while (~scanf("%d%d%d", &n, &m, &k)) {
13 for (int i = 0; i < 15; ++i) vec[i].clear();
14 for (int i = 1; i <= n; ++i) {
15 int a, b, c;
16 scanf("%d%d%d", &a, &b, &c);
17 vec[a].push_back(make_pair(b, c));
18 }
19 memset(dp, -1, sizeof(dp));
20 memset(dp[0], 0, sizeof(dp[0]));
21 for (int i = 1; i <= k; ++i)
22 for (int x = 0; x < (int) vec[i].size(); ++x) {
23 int p = vec[i][x].first;
24 for (int j = m; j >= p; --j) {
25 int v = vec[i][x].second;
26 if (dp[i][j - p] != -1)
27 dp[i][j] = max(dp[i][j - p] + v, dp[i][j]);
28 if (dp[i - 1][j - p] != -1)
29 dp[i][j] = max(dp[i][j], dp[i - 1][j - p] + v);
30 }
31 }
32 if (dp[k][m] != -1)
33 printf("%d\n", dp[k][m]);
34 else
35 printf("Impossible\n");
36 }
37 return 0;
38 }
E - AreYouBusy HDU - 3535（混合背包）
给你n个集合，刚开始有m元。 所有数据范围都 <= 100
下面对n个集合的描述输入 x，s 表示第i个集合有x件商品，s描述该集合的性质
(s == 0:至少买一件 s == 1:至多买一件 s == 2:数量没限制)
下面x行，给出p，v 给出第i件商品的价格和价值。
思想和上面的D题差不多，因为当前组需要通过上一组的合法状态得到，或者由组内的合法状态得到
我们考虑3种情况：
对于3种情况如何初始化也是一个问题:
对于至少买1件的，一开始本组都是不合法的，而对于其他两种情况，是站在前面的情况下更新本组的，相当于继承前一组的状态，所以要复制前一组的内容
如果用以上的方法写，还需要注意本题最坑的一点，就是存在p为0的情况。
1 #include <iostream>View Code
2 #include <cstdio>
3 #include <algorithm>
4 #include <cstring>
5 #include <vector>
6 using namespace std;
7 const int M = 100 + 5;
8 const int N = 100 + 5;
9
10 int n, m, s[N];
11 vector < pair <int, int> > vec[N];
12 int dp[N][M];
13
14 int main() {
15 //freopen("in.txt", "r", stdin);
16 while (~scanf("%d%d", &n, &m)) {
17 for (int i = 0; i < N; ++i) vec[i].clear();
18 int x, y, p, v;
19 for (int i = 1; i <= n; ++i) {
20 scanf("%d%d", &x, &y);
21 s[i] = y;
22 while (x--) {
23 scanf("%d%d", &p, &v);
24 vec[i].push_back(make_pair(p, v));
25 }
26 }
27 memset(dp, 0, sizeof(dp));
28 for (int i = 1; i <= n; ++i) {
29 if (s[i])
30 for (int t = 0; t <= m; ++t) dp[i][t] = dp[i - 1][t];
31 else
32 for (int t = 0; t <= m; ++t) dp[i][t] = -1;
33 for (int x = 0; x < (int) vec[i].size(); ++x) {
34 int p = vec[i][x].first;
35 int v = vec[i][x].second;
36 if (s[i] == 0) {
37 for (int j = m; j >= p; --j) {
38 // 下面两个if的顺序不能错,因为可能存在p为0的情况。
39 // 如果第二个if更新成功,那么再进行第一个if,自身就合法了,就一定会再次更新,一个物品选择了两次
40 // 注意一点:dp[i][j]自身是不合法的,需要通过合法的情况进行更新
41 if (dp[i][j - p] != -1)
42 dp[i][j] = max(dp[i][j], dp[i][j - p] + v);
43 if (dp[i - 1][j - p] != -1)
44 dp[i][j] = max(dp[i][j], dp[i - 1][j - p] + v);
45 }
46 } else if (s[i] == 1) {
47 for (int j = m; j >= p; --j) {
48 if (dp[i - 1][j - p] != -1)
49 dp[i][j] = max(dp[i][j], dp[i - 1][j - p] + v);
50 }
51 } else {
52 for (int j = m; j >= p; --j) {
53 if (dp[i][j - p] != -1)
54 dp[i][j] = max(dp[i][j], dp[i][j - p] + v);
55 }
56 }
57 }
58 }
59 printf("%d\n", dp[n][m]);
60 }
61 return 0;
62 }
对于本题数据范围小，而且存在p为0的情况，可以通过初始化为-INF，来直接避免考虑细节，详见代码，而且组的顺序不影响dp，代码量减少很多
1 #include <cstdio>View Code
2 #include <algorithm>
3 #include <cstring>
4 using namespace std;
5 const int N = 100 + 5;
6 const int INF = 0x3f3f3f3f;
7
8 int n, m, s, x;
9 int dp[N][N], p[N], v[N];
10
11 int main() {
12 //freopen("in.txt", "r", stdin);
13 while (~scanf("%d%d", &n, &m)) {
14 memset(dp, 0, sizeof(dp));
15 for (int i = 1; i <= n; ++i) {
16 scanf("%d%d", &x, &s);
17 for (int j = 1; j <= x; ++j) scanf("%d%d", &p[j], &v[j]);
18 for (int j = 0; j <= m; ++j)
19 dp[i][j] = s ? dp[i - 1][j] : -INF;
20 for (int k = 1; k <= x; ++k) {
21 if (s == 0) {
22 for (int j = m; j >= p[k]; --j)
23 dp[i][j] = max(dp[i][j], max(dp[i][j - p[k]] + v[k], dp[i - 1][j - p[k]] + v[k]));
24 } else if (s == 1) {
25 for (int j = m; j >= p[k]; --j)
26 dp[i][j] = max(dp[i][j], dp[i - 1][j - p[k]] + v[k]);
27 } else {
28 for (int j = m; j >= p[k]; --j)
29 dp[i][j] = max(dp[i][j], dp[i][j - p[k]] + v[k]);
30 }
31 }
32 }
33 printf("%d\n", max(dp[n][m], -1));
34 }
35 return 0;
36 }
F - CD UVA - 624（记录路径的01背包）
给你n个数，和一个sum，让你找这n个数的一个序列，使得和最接近n
参照背包九讲中的方法，这里我们用一维的01背包写，用一维是因为写了二维的时候发现，二维最后存的情况会少，所以二维的意义也只是求个maxn。
记录方法和上面讲的差不多，但是题目要求的是顺序给出选择的数。如果常规地顺序遍历数组，最后还需要从后往前逆推出答案存到vector或者数组中，
还要再逆序输出。不妨背包遍历数组的时候，就逆序遍历，就可以正推答案，也省去了存入的操作，可以直接输出。
1 #include <cstdio>View Code
2 #include <cstring>
3 #include <algorithm>
4 using namespace std;
5 const int M = 1e4 + 5;
6
7 int dp[M], vis[25][M];
8 int a[25], n, m;
9
10 int main() {
11 freopen("in.txt", "r", stdin);
12 while (~scanf("%d%d", &n, &m)) {
13 for (int i = 1; i <= m; ++i) scanf("%d", &a[i]);
14 memset(dp, 0, sizeof(dp));
15 memset(vis, 0, sizeof(vis));
16 for (int i = m; i >= 1; --i)
17 for (int j = n; j >= a[i]; --j) {
18 dp[j] = max(dp[j], dp[j - a[i]] + a[i]);
19 if (dp[j] == dp[j - a[i]] + a[i])
20 vis[i][j] = 1;
21 }
22 int j = n;
23 for (int i = 1; i <= m; ++i)
24 if (vis[i][j]) {
25 printf("%d ", a[i]);
26 j -= a[i];
27 }
28 printf("sum:%d\n", dp[n]);
29 }
30 return 0;
31 }
G - Dividing coins UVA - 562（转化成01背包）
给你n个数，让你把它分成两堆，使得两堆的和之差尽量小，求这个差值。
换个说法就是，既然可以分成两堆，那么就是找存在和为sum的方案数，以及和为n - sum的方案数也存在的情况，使abs(2 * sum - n)尽量小
背包九讲中说:直接把01背包那里的max改为sum就行，因为已经遍历了所有可能的组成情况。这样题目就很简单了。dp[i] 表示和为 i 的方案数。
1 #include <iostream>View Code
2 #include <cstdio>
3 #include <algorithm>
4 #include <cstring>
5 using namespace std;
6 const int N = 100 + 5;
7 const int M = 5e4 + 5;
8
9 int a[N];
10 int dp[M];
11
12 int main() {
13 int t; scanf("%d", &t);
14 while (t--) {
15 int n; scanf("%d", &n);
16 int sum = 0;
17 for (int i = 1; i <= n; ++i) {
18 scanf("%d", &a[i]);
19 sum += a[i];
20 }
21 memset(dp, 0, sizeof(dp));
22 dp[0] = 1;
23 for (int i = 1; i <= n; ++i)
24 for (int j = sum; j >= a[i]; --j)
25 dp[j] += dp[j - a[i]];
26 int ans = sum;
27 for (int i = 1; i <= sum; ++i)
28 if (dp[i] && dp[sum - i])
29 ans = min(ans, abs(sum - i * 2));
30 printf("%d\n", ans);
31 }
32
H - Dollars UVA - 147（转化成完全背包）
给你很多种面值的硬币，让你求构成面值和为sum的方案数，硬币数量不限制
和G题基本一样，就是把换成完全背包的写法，状态转移方程不变。还有一个坑点，就是浮点数转化成整数有误差。
1 /*View Code
2 double 保证小数点后15位准确
3 坑点: 18.90 * 100 = 1889 (精度误差得可怕)
4 无误差的方法(一般不用):
5 (tmp * 1000 - tmp * 100) / 9;
6 更常用的方法:
7 (tmp + eps) * 100 eps足够小
8 */
9 #include <cstdio>
10 #include <cstring>
11 using namespace std;
12 const double eps = 1e-6;
13 const int M = 3e4 + 5;
14
15 int m;
16 long long dp[M];
17 int a[11] = {5, 10, 20, 50, 100, 200, 500, 1000, 2000, 5000, 10000};
18
19 void init() {
20 dp[0] = 1;
21 for (int i = 0; i < 11; ++i)
22 for (int j = a[i]; j <= 30000; ++j)
23 dp[j] += dp[j - a[i]];
24 }
25
26 int main() {
27 init();
28 double tmp;
29 while (~scanf("%lf", &tmp) && tmp) {
30 m = (tmp + eps) * 100;
31 printf("%6.2lf%17lld\n", tmp, dp[m]);
32 }
33 return 0;
34 }
K - Dollar Dayz POJ - 3181（完全背包+大数相加）
和H题基本一样，但是long long长度都存不下方案数，只能模拟下大数相加，还有垃圾POJ支持性真差，CE好几次
1 #include <iostream>View Code
2 #include <cstdio>
3 #include <algorithm>
4 #include <string>
5 #include <cstring>
6 using namespace std;
7 const int N = 100 + 5;
8 const int M = 1000 + 5;
9
10 int n, k, a[N];
11 string dp[M];
12
13 string sum(string s1, string s2) {
14 if (s1.size() < s2.size())
15 swap(s1, s2);
16 for (int i = s1.size() - 1, j = s2.size() - 1; i >= 0; --i, --j) {
17 s1[i] = char (s1[i] + (j >= 0 ? s2[j] - '0' : 0));
18 if (s1[i] - '0' >= 10) {
19 s1[i] = char ((s1[i] - '0') % 10 + '0');
20 if (i) s1[i - 1]++;
21 else s1 = "1" + s1;
22 }
23 }
24 return s1;
25 }
26
27 int main() {
28 for (int i = 1; i <= 100; ++i) a[i] = i;
29 while (~scanf("%d%d", &n, &k)) {
30 memset(dp, 0, sizeof(dp));
31 dp[0] = "1";
32 for (int i = 1; i <= k; ++i)
33 for (int j = a[i]; j <= n; ++j)
34 dp[j] = sum(dp[j], dp[j - a[i]]);
35 cout << dp[n] << endl;
36 }
37 return 0;
38 }
N - Cash Machine POJ - 1276（多重背包）
模板题，就不解释了
1 #include <cstdio>View Code
2 #include <algorithm>
3 #include <cstring>
4 using namespace std;
5 const int M = 1e5 + 5;
6
7 int m, n, dp[M];
8 int c[15], v[15];
9
10 int main() {
11 while (~scanf("%d%d", &m, &n)) {
12 for (int i = 1; i <= n; ++i) scanf("%d%d", &c[i], &v[i]);
13 memset(dp, 0, sizeof(dp));
14 for (int i = 1; i <= n; ++i)
15 if (v[i] * c[i] >= m) {
16 for (int j = v[i]; j <= m; ++j)
17 dp[j] = max(dp[j], dp[j - v[i]] + v[i]);
18 } else {
19 int k = 1;
20 while (k < c[i]) {
21 for (int j = m; j >= k * v[i]; --j)
22 dp[j] = max(dp[j], dp[j - k * v[i]] + k * v[i]);
23 c[i] -= k;
24 k <<= 1;
25 }
26 for (int j = m; j >= v[i] * c[i]; --j)
27 dp[j] = max(dp[j], dp[j - v[i] * c[i]] + v[i] * c[i]);
28 }
29 printf("%d\n", dp[m]);
30 }
31 return 0;
32 }
O - Space Elevator POJ - 2392（01背包）
给出n种石头的高度，最大高度限制（只能放在这个高度之下），数量。求用这些石头能垒起来的最大高度。按每种石头的最大限制高度排个序，就很水了。
1 #include <cstdio>View Code
2 #include <cstring>
3 #include <algorithm>
4 using namespace std;
5 const int M = 4e4 + 5;
6
7 int n, dp[M];
8
9 struct node {
10 int h, limit, num;
11 } a[405];
12
13 bool cmp(node a, node b) {
14 return a.limit < b.limit;
15 }
16
17 int main() {
18 while (~scanf("%d", &n)) {
19 for (int i = 1; i <= n; ++i)
20 scanf("%d%d%d", &a[i].h, &a[i].limit, &a[i].num);
21 sort(a + 1, a + n + 1, cmp);
22 memset(dp, 0, sizeof(dp));
23 for (int i = 1; i <= n; ++i)
24 for (int k = 1; k <= a[i].num; ++k)
25 for (int j = a[i].limit; j >= a[i].h; --j)
26 dp[j] = max(dp[j], dp[j - a[i].h] + a[i].h);
27 int ans = 0;
28 for (int i = 0; i <= a[n].limit; ++i) ans = max(ans, dp[i]);
29 printf("%d\n", ans);
30 }
31 return 0;
32 }
T - ACboy needs your help HDU - 1712（分组背包）
给出n门课程，和m的时间。下面给出n×m的矩阵，a[ i ][ j ]：花 j 的时间在第 i 门课程上，得到的成绩为a[ i ][ j ]，求所有课程的成绩总和的最大值。
分组背包裸题，照着伪代码翻译一遍就行
1 #include <cstdio>View Code
2 #include <algorithm>
3 #include <cstring>
4 using namespace std;
5
6 int n, m;
7 int a[105][105];
8 int dp[105];
9
10 int main() {
11 while (~scanf("%d%d", &n, &m)) {
12 if (m == 0 && n == 0) break;
13 for (int i = 1; i <= n; ++i)
14 for (int j = 1; j <= m; ++j)
15 scanf("%d", &a[i][j]);
16 memset(dp, 0, sizeof(dp));
17 for (int i = 1; i <= n; ++i)
18 for (int j = m; j >= 0; --j)
19 for (int k = 1; k <= m; ++k)
20 if (j >= k) dp[j] = max(dp[j], dp[j - k] + a[i][k]);
21 printf("%d\n", dp[m]);
22 }
23 return 0;
24 }
U - 饭卡 HDU - 2546（01背包）
给出n个菜的价格和卡上的余额m元，每个菜只能买一次，当卡上的余额>=5时，一定可以购买成功(即使购买后卡上余额为负)
否则无法购买(即使金额足够)，求卡上的余额可能的最小值。
要使卡上余额尽量小，最后应该留下 >=5 的最小余额，然后去买最贵的菜。再注意特判以下 < 5 时的结果。水题 WA 2 发...
1 #include <cstdio>View Code
2 #include <algorithm>
3 #include <cstring>
4 using namespace std;
5 const int N = 1000 + 5;
6
7 int n, m, p[N], dp[N];
8
9 int main() {
10 while (~scanf("%d", &n) && n) {
11 for (int i = 1; i <= n; ++i) scanf("%d", &p[i]);
12 sort(p + 1, p + n + 1);
13 scanf("%d", &m);
14 if (m < 5) {
15 printf("%d\n", m);
16 continue;
17 }
18 memset(dp, 0, sizeof(dp));
19 for (int i = 1; i <= n - 1; ++i)
20 for (int j = m - 5; j >= p[i]; --j)
21 dp[j] = max(dp[j], dp[j - p[i]] + p[i]);
22 printf("%d\n", m - dp[m - 5] - p[n]);
23 }
24 return 0;
25 }
V - 悼念512汶川大地震遇难同胞――珍惜现在，感恩生活 HDU - 2191（01背包变形）
给出n种大米的价格，重量，数量，求用m元能买到的最大的重量。水题。
1 #include <cstring>View Code
2 #include <cstdio>
3 #include <algorithm>
4 using namespace std;
5 const int N = 100 + 5;
6
7 int n, m;
8 int p[N], w[N], num[N], dp[N];
9
10 int main() {
11 int T; scanf("%d", &T);
12 while (T--) {
13 scanf("%d%d", &m, &n);
14 for (int i = 1; i <= n; ++i)
15 scanf("%d%d%d", &p[i], &w[i], &num[i]);
16 memset(dp, 0, sizeof(dp));
17 for (int i = 1; i <= n; ++i)
18 for (int k = 1; k <= num[i]; ++k)
19 for (int j = m; j >= p[i]; --j)
20 dp[j] = max(dp[j], dp[j - p[i]] + w[i]);
21 printf("%d\n", dp[m]);
22 }
23 return 0;
24 }
HDU - 6092 (01背包变形)
给出能组成各种数的方案结果，让你反推原来的数组。
这里就需要对之前求方案数要有足够深的理解：
dp[0] = 1;
for (int i = 1; i <= n; ++i)
for (int j = m; j >= a[i]; --j)
dp[j] += dp[j - a[i]];
上面是不断地考虑a[i],更新当前方案数。
那么对于本题中B数组的定义会发现就是上面求得的dp数组。反推，该怎么还原a数组呢？
首先dp[i]表示组成i的方案数，那么去除所有由小于i 的a[]组成的方案数，如果此时dp[i]非0，那么就是i的个数了。
另外还会发现，除dp[0]外的第一个非 0 dp[i]就是 i 的个数，所以可以从这里开始。
因为是反推，在更新的时候应该是反过来， dp[j] -= dp[j - i]
1 #include <cstdio>View Code
2 #include <algorithm>
3 using namespace std;
4 const int N = 1e4 + 5;
5 typedef long long LL;
6
7 int n, m, a[N];
8 LL dp[N];
9
10 int main() {
11 int T; scanf("%d", &T);
12 while (T--) {
13 scanf("%d%d", &n, &m);
14 for (int i = 0; i <= m; ++i) scanf("%lld", &dp[i]);
15 int i = 1, cnt = 0;
16 while (cnt < n) {
17 if (dp[i]) {
18 a[cnt++] = i;
19 for (int j = i; j <= m; ++j)
20 dp[j] -= dp[j - i];
21 } else i++;
22 }
23 for (int i = 0; i < n; ++i)
24 printf("%d%s", a[i], i == n - 1 ? "\n" : " ");
25 }
26 return 0;
27 }