背包问题 ——第K优解 或 次优解

附上水题一枚：Bone Collector II

http://acm.hdu.edu.cn/showproblem.php?pid=2639

———摘自背包九讲

将每个状态都表示成有序队列，将状态转移方程化成有序队列的合并（归并的思想），增加一个维度

附上代码：

<span style="font-size:14px;color:#333399;">#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
struct node
{
    int w,v;
}p[110];
int dp[1100][31];
int a[31],b[31];
int main()
{
    int n,m,k,T,d;
    cin>>T;
    while(T--){
        scanf("%d%d%d",&n,&m,&k);
        for(int i=0;i<n;i++) scanf("%d",&p[i].w);
        for(int i=0;i<n;i++) scanf("%d",&p[i].v);
        memset(dp,0,sizeof dp);
        for(int i=0;i<n;i++){
            for(int j=m;j>=p[i].v;j--){
                for(d=1;d<=k;d++){
                    a[d]=dp[j-p[i].v][d]+p[i].w;
                    b[d]=dp[j][d];
                }
                a[d]=b[d]=-1;
                int x=1,y=1,z=1;
                while(z<=k&&(x<=k||y<=k)){     //开始合并，时间复杂度为O(K)
                    if(a[x]>b[y]){
                        dp[j][z]=a[x++];
                    }
                    else{
                        dp[j][z]=b[y++];
                    }
                    if(dp[j][z]!=dp[j][z-1]) z++; //合并结束
                }
            }
        }
        cout<<dp[m][k]<<endl;

    }

    return 0;
}</span>