首页 > 代码库 > 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优解