HDU 2639 第K大背包问题

 1 //状态方程和01背包类似，dp[j][k]表示背包容量为j的第k大背包的值。。。。。。。。。。
 2 
 3 //应当注意的是此时dp[j][1.....k]应当是递减的。。。。。。。。。。。。。。。。。。。。
 4 
 5 
 6 #include<stdio.h>
 7 
 8 #include<string.h>
 9 #define Max(x,y) (x>y?x:y)
10 #define max_v 1000+10
11 #define max_k 30+5
12 #define max_n 100+5
13 
14 int dp[max_v][max_k],w[max_n],c[max_n];
15 int q1[max_k],q2[max_k];
16 
17 int main(){
18     int t;
19     scanf("%d",&t);
20     while(t--){
21         int n,v,k;
22         scanf("%d%d%d",&n,&v,&k);
23         memset(dp,0,sizeof(dp));
24         for(int i=1;i<=n;i++){
25             scanf("%d",&w[i]);
26         }
27         for(int i=1;i<=n;i++){
28             scanf("%d",&c[i]);
29         }
30         for(int i=1;i<=n;i++){
31             for(int j=v;j>=c[i];j--){
32                 for(int kk=1;kk<=k;kk++){
33                     q1[kk]=dp[j-c[i]][kk]+w[i];
34                     q2[kk]=dp[j][kk];
35                 }
36                 q1[k+1]=q2[k+1]=-1;
37                 int h=1,h1=1,h2=1;
38                 while(h<=k&&(h1<=k||h2<=k)){
39                     if(q1[h1]>q2[h2]){
40                         dp[j][h]=q1[h1];
41                         h1++;
42                     }
43                     //else if(q1[h1]<q2[h2]){
44                     else{
45                         dp[j][h]=q2[h2];
46                         h2++;
47                     }
48                         if(dp[j][h]!=dp[j][h-1]){
49                         h++;
50                     }
51                 }
52             }
53         }
54       //      for(int i=1;i<=k;i++){
55     //        printf("%d ",dp[v][i]);
56     //    }
57     //    puts("");
58         printf("%d
",dp[v][k]);
59     }
60 }