这是道好题。至少我错了不下10次。dp的两个重点：转移方程+初始化。偶敢保证，偶的转移方程绝对没问题。可是初始化上wa到shi了。昨天想了整整一晚上，跟经典01背包那么像，加上一个容器就写不出来了。然后问鱼神，鱼神说这题的数据人畜无害，哄小盆友的。我了个去！然后问他思路，说设f[i][j][k]，表示前i个中挑j个占容量是k时的最大value，然后就没有然后了。。。
我自己就在那列各种状态，各种推导。思路还是很模糊，后来又好几次问鱼神。甚至有几次让我问的直接不鸟我了。T_T悲摧的人生啊。。。
后来推出：
f[i][j][k] = max(f[i-1][j][k], f[i-1][j-1][k - c[i]] + w[i]);
转移方程出来我以为这题差不多就过了，可恨的是这是一个满背包。01背包时，满背包处理是f[1..n][0] = 0, 其余都等于-∞，可是这按照这个思路把f[1..N][0][1..L]初始化成0，其余是-∞却不对。wa了有十几次。最后根据背包九讲里简化01背包空间复杂度的方法把三维数组化成二维的。f[j][k]表示挑满j个物品占容量为k时的最大value。
f[j][k] = max(f[j][k], f[j-1][k-c[i]] + w[i]) （类比经典01背包简化， f[i] = max(f[i], f[i-c[i]] + w[i])）.
然后通过经典01背包简化过后的写法：
1 for i=1..N
2 for v=V..0
3 f[v]=max{f[v],f[v-c[i]]+w[i]};
因为f[i][v]是从f[i-1][v-c[i]] + w[i] 推出的。如果v = 0...V的话就成了。f[i][v] = f[i][v-c[i]]。
这题的转移过程就是：
1 for(i = 1; i <= n; i++) {
2 for(j = m; j - 1 >= 0; j--) {
3 for(k = l; k > 0 && k - c[i] >= 0; k--) {
4 f[j][k] = max(f[j][k], f[j-1][k-c[i]] + w[i]);
5 }
6 }
7 }
初始化跟上面三维数组写法一样。f[0][1...L] = 0, 其他都是-∞。还得加上一个限制，当前一个不能背满时，不转移。
1 for(k = l; k > 0 && k - c[i] >= 0; k--) {
2 if(f[j-1][k-c[i]] != inf)
3 f[j][k] = max(f[j][k], f[j-1][k-c[i]] + w[i]);
4 }
My Code:
View Code
1 #include <iostream>
2 #include <cstring>
3 #include <cstdio>
4
5 using namespace std;
6
7 const int N = 107;
8 const int M = 1024;
9 const int inf = -(~0u>>2);
10
11 int f[N][M];
12 int c[N], w[N];
13
14 int main() {
15 //freopen("data.in", "r", stdin);
16
17 int i, j, k;
18 int n, m, l, t;
19 scanf("%d", &t);
20 while(t--) {
21 scanf("%d%d%d", &n, &m, &l);
22 for(i = 1; i <= n; i++) {
23 scanf("%d%d", &c[i], &w[i]);
24 }
25 for(j = m; j >= 0; j--) {
26 for(k = l; k >= 0; k--)
27 f[j][k] = inf;
28 }
29 for(i = 0; i <= l; i++) {
30 f[0][i] = 0;
31 }
32 for(i = 1; i <= n; i++) {
33 for(j = m; j - 1 >= 0; j--) {
34 for(k = l; k > 0 && k - c[i] >= 0; k--) {
35 if(f[j-1][k-c[i]] != inf)
36 f[j][k] = max(f[j][k], f[j-1][k-c[i]] + w[i]);
37 }
38 }
39 }
40 //cout << inf << endl;
41 if(f[m][l] == inf) {cout << '0' << endl; continue;}
42 cout << f[m][l] << endl;
43 }
44 return 0;
45 }
ps：有人直接秒过了，Orz！不过我觉得好题应该好做。^_^。