hdu 2639 Bone Collector II （01背包，求第k优解）

这题和典型的01背包求最优解不同，是要求第k优解，所以，最直观的想法就是在01背包的基础上再增加一维表示第k大时的价值。
具体思路见下面的参考链接，说的很详细

参考连接：
http://laiba2004.blog.163.com/blog/static/8835120220138611342496/
http://hi.baidu.com/chenyun00/item/1c6c44318acc8bfaa88428c7

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

const int maxn=;

const int maxv=;

const int maxk=;

int n,v,k;

int dp[maxv][maxk];  //dp[j][k]表示容量为j时，第k大的值

int w[maxn];  //价值

int vv[maxn];  //容量

//一开始tmp只开了maxk个大小，导致WA。。。因为对应的每个k，有dp[j][z]和dp[j-vv[i]][z]+w[i]两个状态，所以要开2*maxk大小

//int tmp[maxk*2];

int tmp1[maxk*];

int tmp2[maxk*];

int main()

{

    int t,idx,cnt;

    scanf("%d",&t);

    while(t--){

        scanf("%d%d%d",&n,&v,&k);

        for(int i=;i<=n;i++)

            scanf("%d",&w[i]);  //价值

        for(int i=;i<=n;i++)

            scanf("%d",&vv[i]); //容量

        memset(dp,,sizeof(dp));

        for(int i=;i<=n;i++){

            for(int j=v;j>=vv[i];j--){

                //idx=0;

                for(int z=;z<=k;z++){

                    tmp1[z]=dp[j][z];

                    tmp2[z]=dp[j-vv[i]][z]+w[i];

                }

                /*

                sort(tmp+1,tmp+idx+1);

                cnt=1;

                dp[j][1]=tmp[idx];

                for(int q=idx-1;q>=1&&cnt<k;q--){

                    if(tmp[q]!=tmp[q+1])

                        dp[j][++cnt]=tmp[q];

                }

                while(cnt<k){

                    dp[j][++cnt]=0;

                }

                */

                //其实不需要按照上面用排序，可以用开两个数组tmp1和tmp2存储，这两个数组都是有序序列

                //这样的话，从原本的931ms减少到125ms

                tmp1[k+]=-;tmp2[k+]=-; //将tmp1和tmp2的第k+1个元素设为-1，即设成较小的值

                int a=,b=;

                cnt=;

                while(cnt<k && (a!=k+||b!=k+)){

                    if(tmp1[a]>tmp2[b]){

                        dp[j][++cnt]=tmp1[a];

                        a++;

                    }

                    else{

                        dp[j][++cnt]=tmp2[b];

                        b++;

                    }

                    if(dp[j][cnt]==dp[j][cnt-])

                        cnt--;

                }

            }

        }

        printf("%d\n",dp[v][k]);

    }

    return ;

}