HDU 2639 Bone Collector II （DP 第k优解）

题意：输入t，t组测试样例，每组样例输入 n, v, k. 接着输入n个物品的价值，再输入n个物品的体积。求k优解。

分析：dp[n][v][k]表示n个物品，在体积不超过v的情况，第k大的值是多少。dp[i][v][k]与dp[i-1][v][k]与dp[i-1][v-volume[i]]+value[i]有关。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>

using namespace std;

const int maxn = 105;

int value[maxn];
int volume[maxn];
int dp[maxn*10][50];
int a[50];

bool cmp(int x1, int x2)
{
    return x1>x2;
}

int main()
{
    int n, v, k;
    int t;
    scanf("%d", &t);
    while(t--)
    {
        scanf("%d%d%d", &n, &v, &k);
        for(int i=1; i<=n; i++)
            scanf("%d", &value[i]);
        for(int i=1; i<=n; i++)
            scanf("%d", &volume[i]);
        memset(dp, 0, sizeof(dp));
        for(int i=1; i<=n; i++)
        {
            for(int j=v; j>=volume[i]; j--)
            {
                int kk = 1;
                for(int ij=1; ij<=k; ij++)
                {
                    a[kk++] = dp[j-volume[i]][ij]+value[i];
                    a[kk++] = dp[j][ij];
                }
                sort(a+1, a+kk, cmp);
                kk = unique(a+1, a+kk)-a-1;
                for(int ij=1; ij<=k; ij++)
                {
                    if(ij>kk)
                        dp[j][ij] = 0;
                    else
                        dp[j][ij] = a[ij];
                }
            }
        }
        printf("%d
", dp[v][k]);
    }

    return 0;
}