hdu-2639 01背包 第K优决策

本文主要是介绍hdu-2639 01背包 第K优决策，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

/*
比喻吧：如果想知道学年最高分，那么，只要知道每个班级的最高分，
然后统计一遍就可以了。如果想知道学年前十呢？必须要知道每个班的前十名。
心里模拟一下，这就是本题核心的算法。
两种决策，就可以看作这个学年只有两个班。
*/
#include "stdio.h"
#include "string.h"
int n,V,kth;
int v[105],p[105],dp[1005][35];  //价值 体积
int A[35],B[35];
void kth_ZeroOnePack()
{int i,j,k;memset(dp,0,sizeof(dp));for( i=1;i<=n;i++ ){for( j=V;j>=v[i];j-- ){for(k=1;k<=kth;k++){A[k]=dp[j-v[i]][k]+p[i];B[k]=dp[j][k];}A[k]=B[k]=-1;int a,b,c;a=b=c=1;while( c<=kth && (A[a]!=-1 || B[b]!=-1)){if(A[a]>B[b])dp[j][c]=A[a++];elsedp[j][c]=B[b++];if(dp[j][c]!=dp[j][c-1])c++;}}}printf("%d\n",dp[V][kth]);
}int main()
{int t,i;scanf("%d",&t);while( t-- ){scanf("%d%d%d",&n,&V,&kth);for( i=1;i<=n;i++ ){scanf("%d",&p[i]);}for( i=1;i<=n;i++ ){scanf("%d",&v[i]);}kth_ZeroOnePack();}return 0;
}

这篇关于hdu-2639 01背包 第K优决策的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---