HDU 2159 FATE(動的企画dpの二次元完全リュックサック問題)

住所:http://acm.hdu.edu.cn/showproblem.php?pid=2159
構想:動的企画dpの二次元完全リュックサック問題
状態方程式が鍵です....
//***dp[j]=Max(dp[j]、[l],dp[J-1][l-b[i]+a[i] l点を使った忍耐度を表し、j個のモンスターを殺した後の最大の経験数を表します.  
テーマ分析:
二次元の費用のリュックサックの問題は、それぞれのものに対して、二つの異なる費用があるということです.この品物を選ぶには、この二つの代価が必要です.それぞれの対価には最大値(バックパック容量)があります.物を選ぶにはどうすれば一番大きな価値がありますか?この2つの対価をそれぞれ1と2とし、i番目のものに必要な2つの対価をそれぞれa[i]とb[i]とする.2つの対価で支払うことができる最大値(2つのバックパック容量)はそれぞれVとUである.物の価値はw[i]です.
費用は1次元を追加しました.状態だけでも1次元を追加すればいいです.f[v][u]は前のiのものがそれぞれvとuの二つの代価を払った時に得られる最大の価値を表します.状態移行の方程式は以下の通りです.
f[v][u]=max｛f[i-1][v]、[u],f[v-a[i]、[u-b[i]＋w[i]｝
上記の方法のように、2次元の配列のみを使用してもよい.各アイテムが一回しか取れない場合、変数vとuは逆順のループを採用し、完全なバックパックのような物品がある場合は順番のループを採用する.荷物が複数のリュックサックのような問題がある場合、物を分割します.
ここに来ても、そろそろ考えがあるかもしれません.コードを見れば、二次元料金のリュックサックがよく分かります.
まず、完全なバックパックのテンプレートを見てみます.
void Complette Pack(intvalue,int weight)｛ int i; for(i=weight;i<=V;i+)  dp[i]=max(dp[i],dp[i-weight]+value);   }
コードは以下の通りです

 1 #include<stdio.h>

 2 #include<string.h>

 3 #define N 110

 4 int dp[N][N];//    

 5 int a[N],b[N];

 6 int max(int x,int y)

 7 {

 8     return x>y?x:y;

 9 }

10 int main()

11 {

12     int n,m,k,s,i,j,l;

13     while(scanf("%d%d%d%d",&n,&m,&k,&s)!=EOF)  //n   ，m    ，k     ，s      

14     {

15         for(i=0;i<k;i++)

16         scanf("%d%d",&a[i],&b[i]);  //              

17         memset(dp,0,sizeof(dp));

18         for(i=0;i<k;i++)  //      

19         { 

20             for(j=1;j<=s;j++)  //    ，      s

21             {

22                 for(l=b[i];l<=m;l++)  //          for  

23                   dp[j][l]=max(dp[j][l],dp[j-1][l-b[i]]+a[i]); //dp[j][l]       l     ，    j   ，         

24             }

25         }

26         for(i=0;i<=m;i++)   //i    0   m   dp[j][l]       l     ，    j   ，         

27           if(dp[s][i]>=n) break;  //    m     ，    s    ,         

28         if(dp[s][i]<n)   //break               。。。 

29           printf("-1
");  //      s                            -1  

30         else

31           printf("%d
",m-i);  ////   s    ，   i      ，            m-i

32     }

33     return 0;

34 } 

35