首页 > 代码库 > hdu2639（背包求第k优解）
hdu2639（背包求第k优解）
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2639
题意：给出一行价值，一行体积，让你在v体积的范围内找出第k大的值
分析：dp[i][j][k]表示前i个物品容积为j时的第k优解。那么对于每种状态dp[i][j]都需要维护好前k优解。
每次根据前k优解进行每种取或不取第i件物品，用数组a记录取第i件物品，数组b记录不取，这样
数组a，b了所有能组成j的x种解，最后在x里取前k优解记录下来就好。剩下的肯定不是前k优解了。。。
#include <cstdio>#include <cstring>#include <cmath>#include <iostream>#include <algorithm>#include <queue>#include <cstdlib>#include <vector>#include <set>#include <map>#define LL long long#define mod 1000000007#define inf 0x3f3f3f3f#define N 10010using namespace std;int p[110],w[110],dp[1010][50],a[50],b[50];int main(){ int t,n,v,k; scanf("%d",&t); while(t--) { scanf("%d%d%d",&n,&v,&k); memset(dp,0,sizeof(dp)); for(int i=1; i<=n; i++)scanf("%d",&p[i]); for(int i=1; i<=n; i++)scanf("%d",&w[i]); for(int i=1; i<=n; i++) { for(int j=v; j>=w[i]; j--) { for(int l=1; l<=k; l++)//组成体积为j无非就是j-w[i]状态加上第i件和不取第i件，最多有2k种 { a[l]=dp[j-w[i]][l]+p[i]; b[l]=dp[j][l]; } a[k+1]=-1; b[k+1]=-1; int x,y,z; x=y=z=1; while(z<=k&&(a[x]!=-1||b[y]!=-1))//在最多2k种里取最大的k个解并有序存入 { if(a[x]>b[y]) { dp[j][z]=a[x]; x++; } else { dp[j][z]=b[y]; y++; } if(dp[j][z]!=dp[j][z-1])z++; } } } printf("%d\n",dp[v][k]); }}
hdu2639（背包求第k优解）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。