HDU_3496 Watch The Movie (背包)

时间:2023-01-03 16:10:41

  这是道好题。至少我错了不下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:


HDU_3496 Watch The Movie (背包)HDU_3496 Watch The Movie (背包)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!不过我觉得好题应该好做。^_^。