背包问题第k优解

转载自：http://blog.csdn.net/daxiongrong/article/details/6061420

题目:多人背包   问题编号:123     RQNOJ



题目描述
DD 和好朋友们要去爬山啦！他们一共有 K 个人，每个人都会背一个包。这些包的容量是相同的，都是 V。可以装进背包里的一共有 N 种物品，每种物品都有给定的体积和价值。

在 DD 看来，合理的背包安排方案是这样的：

每个人背包里装的物品的总体积恰等于包的容量。 
每个包里的每种物品最多只有一件，但两个不同的包中可以存在相同的物品。 
任意两个人，他们包里的物品清单不能完全相同。 
在满足以上要求的前提下，所有包里的所有物品的总价值最大是多少呢？





这里要注意的： 用q1和q2记录，保持递增，合并成前k优解。  要使得背包恰好装满，就要赋初值-maxint，而当背包容量为0时，赋值0。



[cpp] view plaincopy
#include<iostream>  
using namespace std;  
long f[51][50001];  
int q1[51];  
int q2[51];  
int main()  
{   
    //freopen("in.txt","r",stdin);  
    int k,v,n;  
    int value,weight;  
    cin>>k>>v>>n;  
    for(int i=0;i<=k;i++)  
        for(int j=0;j<=v;j++)  
            f[i][j]=INT_MIN;  
    f[1][0]=0;  
    for(int i=1;i<=n;i++)   
    {  
        cin>>weight>>value;  
        for(int j=v;j>=weight;j--){  
            for(int w=1;w<=k;w++){  
            q1[w]=f[w][j];  
            q2[w]=f[w][j-weight]+value;  
            }  
            int h1=1,h2=1,h=0;  
            while(h<k){  
                h++;  
                if(q1[h1]>q2[h2]) {  
                    f[h][j]=q1[h1];  
                    h1++;  
                }  
                else {  
                    f[h][j]=q2[h2];  
                    h2++;  
                }  
            }  
        }  
    }  
        int ans=0;  
        for(int i=1;i<=k;i++)  
            ans+=f[i][v];  
        cout<<ans<<endl;  
        return 0;  
}