rqnoj-123-多人背包-第K最优解（好题）

这道题目是在01背包的基础上求出前K个最优解。

dp[i][j]: 背包容量为i，第j优解的值。

由于任意两个背包不能完全相同，所以只初始化dp[0][1]=0;

因为要求必须恰好装满，所以其他的初始化为最小。

dp[i][1....k]=max(dp[i][1..k],dp[i-w][1...k]+v);

即dp[i][1....k]中的k个元素为dp[i][1..k]中的k个元素+dp[i-w][1...k]中的k个元素的前k大的元素。

合并两个数组的时候利用归并排序的原理合并。

#include<stdio.h>#include<string.h>#include<iostream>#include<algorithm>#include<math.h>using namespace std;int dp[5050][55];int num[201];void add(int x,int k,int w,int v){    int i;    int t1,t2;    t1=t2=1;    for(i=1;i<=k;i++)    {        if(dp[x][t1]>dp[x-w][t2]+v)        {            num[i]=dp[x][t1];            t1++;        }        else        {            num[i]=dp[x-w][t2]+v;            t2++;        }    }    for(i=1;i<=k;i++)dp[x][i]=num[i];}int main(){    int i,j,k,v,n;    int ws[301];    int vs[301];    while(~scanf("%d%d%d",&k,&v,&n))    {        for(i=0;i<n;i++)        {            scanf("%d%d",&ws[i],&vs[i]);        }        for(i=0;i<=v;i++)        {            for(j=0;j<=k;j++)            {                dp[i][j]=-99999999;            }        }        //for(i=0;i<=v;i++)dp[i][0]=-1;        dp[0][1]=0;        for(i=0;i<n;i++)        {           // cout<<"-------------"<<endl;            for(j=v;j>=ws[i];j--)            {                add(j,k,ws[i],vs[i]);            }        }        int ns=0;        for(i=1;i<=k;i++)        {            if(dp[v][i]<=0)break;            ns+=dp[v][i];        }        cout<<ns<<endl;    }    return 0;}