HDU-2639 Bone Collector ||

HDU-2639 Bone Collector ||

01背包问题，但是需要输出的是可以获得的第 \(k\) 大价值。

思路：

状态定义?

我们要求的是第 \(k\) 大价值，所以当我们得到一个当前第 \(k + 1\) 大的价值的时候，可以直接舍去，因为它一定不是第 \(k\) 大的价值。然后我们又需要知道目前得到的 \(k\) 个价值具体是多少，所以我们在原来 \(01\) 背包的基础上在加一维。

所以我们定义 \(f[i][j][k]\) : 遍历到第 \(i\) 个物品，且体积不超过 \(j\) 时可得的第 \(k\) 大价值是多少?

为了方便，滚动数组优化掉第一个维度，即状态变成 \(f[i][j]\) :体积不超过 \(j\) 时可得的第 \(j\) 大价值是多少。

回想一下 \(01\) 背包的状态转移方程 \(f[i][j] = max(f[i - 1][j],f[i - 1][j - v[i]] + w[i])\)

划分了当前物品选和不选。显然这里的选择会影响到当前状态的 \(k\) 个最大值。

所以我们取出这两种选法对应的 \(2 *k\) 个数，排序成新的 \(k\) 个最大数。

实现:

#include <stdio.h>
#include <algorithm>
using namespace std;
int f[1005][35], wei[105], val[105];
int main()
{
    int _;
    scanf("%d", &_);
    while (_--)
    {
        int n, v, k;
        scanf("%d%d%d", &n, &v, &k);
        for (int i = 1; i <= n; i++)
            scanf("%d", &val[i]);
        for (int i = 1; i <= n; i++)
            scanf("%d", &wei[i]);

        for (int i = 1; i <= v; i++)
            for (int j = 1; j <= k; j++)
                f[i][j] = 0;

        for (int i = 1; i <= n; i++)
        {
            for (int j = v; j >= wei[i]; j--)
            {
                //a数组记录的是不选第 i 个物品的 k 个最大价值
                //b数组记录的是选第 i 个物品的 k 个最大价值
                int a[35] = {0}, b[35] = {0};
                for (int l = 1; l <= k; l++)
                {
                    a[l] = f[j][l];
                    b[l] = f[j - wei[i]][l] + val[i];
                }
                a[k + 1] = b[k + 1] = -1;

                int ai = 1, bi = 1;
                for (int l = 1; l <= k && (a[ai] != -1 || b[bi] != -1); l++)
                {
                    if (a[ai] > b[bi])
                        f[j][l] = a[ai++];
                    else
                        f[j][l] = b[bi++];
                    //相同的数算同一个
                    if (f[j][l] == f[j][l - 1])
                        l--;
                }
            }
        }
        printf("%d\n", f[v][k]);
    }
    return 0;
}