2639-Bone Collector II （01背包之第k優解）

題目鏈接：

http://acm.hdu.edu.cn/showproblem.php?pid=2639

求第k優解的關鍵代碼：

用兩個數組記錄兩種狀態（選擇或不選擇），并且只要記錄前k次。在這兩個數組中都是前k次可能的最優解。所以我們只要把這兩個數組做比較，一直排到k就行了

題目代碼：

 1 #include <iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 using namespace std;
 5 int dp[1005][35],a[35],b[35],val[105],vol[105];
 6 int main()
 7 {
 8     int t,n,v,k,c,d,e;
 9     while(~scanf("%d",&t))
10     {
11         while(t--)
12         {
13             scanf("%d%d%d",&n,&v,&k);
14             for(int i=0;i<n;i++)
15             scanf("%d",&val[i]);
16             for(int i=0;i<n;i++)
17             scanf("%d",&vol[i]);
18             memset(dp,0,sizeof(dp));
19             memset(a,0,sizeof(a));
20             memset(b,0,sizeof(b));
21             for(int i=0;i<n;i++)
22             {
23                 for(int j=v;j>=vol[i];j--)
24                 {
25                     for(int t=1;t<=k;t++)
26                     {
27                         a[t]=dp[j-vol[i]][t]+val[i];
28                         b[t]=dp[j][t];
29                     }
30                     c=d=e=1;
31                     while(e<=k&&(c!=k+1||d!=k+1))
32                     {
33                         if(a[c]>b[d])
34                         dp[j][e]=a[c++];
35                         else
36                         dp[j][e]=b[d++];
37                         if(dp[j][e]!=dp[j][e-1])
38                         e++;
39                     }
40                 }
41             }
42             printf("%d\n",dp[v][k]);
43         }
44     }
45     return 0;
46 }

View Code

轉載于:https://www.cnblogs.com/wang-ya-wei/p/5754571.html

本文來自互聯網用戶投稿，該文觀點僅代表作者本人，不代表本站立場。本站僅提供信息存儲空間服務，不擁有所有權，不承擔相關法律責任。
如若轉載，請注明出處：http://www.pswp.cn/news/395389.shtml
繁體地址，請注明出處：http://hk.pswp.cn/news/395389.shtml
英文地址，請注明出處：http://en.pswp.cn/news/395389.shtml

如若內容造成侵權/違法違規/事實不符，請聯系多彩編程網進行投訴反饋email:809451989@qq.com，一經查實，立即刪除！