リュック9説の7(依存するリュックの問題がある)
6401 ワード
1 /*
2 ， i j， i， j
3 http://acm.hdu.edu.cn/showproblem.php?pid=3449
4 ， ，
5 ，
6 n ， cnt[i]
7 ，
8 ， 2^n+1 ， 。 。
9 ， 2^n+1 。
10 ， 。 01 ， v-c[i]...0
11 dp2[v-c[i]...0]
12
13 */
14 #include <stdio.h>
15 #include <string.h>
16 int dp[100000+10],dp2[100000+10];
17 int box[55],cnt[55],price[55][11],value[55][11];
18 inline int max(const int &a, const int &b)
19 {
20 return a < b ? b : a;
21 }
22 int main()
23 {
24 int n,v,i,j,k;
25 while(scanf("%d%d",&n,&v)!=EOF)
26 {
27 memset(dp,0,sizeof(dp));
28 for(i=1; i<=n; ++i)
29 {
30 scanf("%d%d",&box[i],&cnt[i]);
31 memcpy(dp2,dp,sizeof(dp));
32 for(j=1; j<=cnt[i]; ++j)
33 {
34 scanf("%d%d",&price[i][j],&value[i][j]);
35 for(k=v-box[i]; k>=price[i][j]; --k)// 01 ， dp2[k]
36 dp2[k] = max(dp2[k],dp2[k-price[i][j]]+value[i][j]);
37 }
38 for(k=box[i];k<=v; ++k)
39 dp[k] = max(dp[k],dp2[k-box[i]]);// k ， i
40 }
41 printf("%d
",dp[v]);
42 }
43 return 0;
44 }