首页 > 代码库 > HDU 2639 01背包(分解)
HDU 2639 01背包(分解)
http://acm.hdu.edu.cn/showproblem.php?pid=2639
01背包第k优解,把每次的max分步列出来即可
1 #include<stdio.h> 2 #include<string.h> 3 #include<algorithm> 4 using namespace std; 5 struct Node 6 { 7 int price; 8 int val; 9 }node[1005]; 10 int main() 11 { 12 int T; 13 scanf("%d",&T); 14 while(T--) 15 { 16 int n,v,k,i,dp[1005][31]={0},a[31],b[31]; 17 scanf("%d%d%d",&n,&v,&k); 18 for(i=0;i<n;i++) 19 scanf("%d",&node[i].price); 20 for(i=0;i<n;i++) 21 scanf("%d",&node[i].val); 22 int j; 23 for(i=0;i<n;i++) 24 { 25 for(j=v;j>=node[i].val;j--) 26 { 27 int d; 28 for(d=1;d<=k;d++) //每次max分别存入a[]和b[],最后比较相应的次数 29 { 30 a[d]=dp[j-node[i].val][d]+node[i].price; 31 b[d]=dp[j][d]; 32 } 33 int x,y,z; 34 x=y=z=1; 35 a[d]=b[d]=-1; 36 while(z<=k&&(x<=k||y<=k)) 37 { 38 if(a[x]>b[y]) 39 { 40 dp[j][z]=a[x]; 41 x++; 42 } 43 else 44 { 45 dp[j][z]=b[y]; 46 y++; 47 } 48 if(dp[j][z]!=dp[j][z-1]) 49 z++; 50 } 51 } 52 } 53 printf("%d\n",dp[v][k]); 54 } 55 return 0; 56 }
HDU 2639 01背包(分解)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。