首页 > 代码库 > hdu2639 01背包第K优解
hdu2639 01背包第K优解
#include<iostream>#include<cstdio>#include<algorithm>#include<cstring>#include<cmath>using namespace std;int dp[1005][35],val[1005],vol[1005], A[35],B[35];int main(){ int T,n,v,K,k; scanf("%d",&T); while(T--) { scanf("%d%d%d",&n,&v,&K); for(int i=1; i<=n; i++) scanf("%d",&val[i]); for(int i=1; i<=n; i++) scanf("%d",&vol[i]); memset(dp,0,sizeof(dp)); for(int i=1; i<=n; i++) for(int j=v; j>=vol[i]; j--) { for(k=1; k<=K; k++) { A[k]=dp[j-vol[i]][k]+val[i]; B[k]=dp[j][k]; } A[k]=-1; B[k]=-1; int a=1,b=1,c=1; while(c<=K && (A[a]!=-1 || B[b]!=-1)) { if(A[a]>B[b]) dp[j][c]=A[a++]; else dp[j][c]=B[b++]; if(dp[j][c]!=dp[j][c-1]) c++; } } printf("%d\n",dp[v][K]); } return 0;}
http://acm.hdu.edu.cn/showproblem.php?pid=2639
hdu2639 01背包第K优解
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。