P1858 多人背包

P1858 多人背包

题意:

一共有 \(K\) 个人，每个人的背包容量相同都为 \(V\) ，一共有 \(N\) 种物品，每个人每种物品都最多选一个。要求每个人的选的物品总体积必须等于背包的体积。并且要求这 \(K\) 个的 选法都不相同，求在满足上面要求的前提下，包里物品的总价值是多少？

思路:

要求总和最大，其实就是求，凑成的方案的前 \(K\) 大价值的话，所以就想到了求第 \(K\) 最优解问题。但是主要到该题要求背包容量刚好装满，所以转移的时候，一定要判断前一个状态存在再进行转移。

然后考虑如果保证选出来的 \(K\) 大价值的方案都不同。其实我们分析一下我们转移时的状态。从不选当前物品的前 \(k\) 大不同的方案，选当前物品的前 \(k\) 大不同方案转移过来。从状态上看就知道，这样得到的 $2 \times k $ 个方案肯定是互不相同的，所以直接转移就可以了。

值得注意的是，这里的初始化值，其实是 \(f[0][1] = 0\) 因为没有物品时的第一大值为 0。

实现:

#include <bits/stdc++.h>
using namespace std;
const int N = 205, M = 5005;
int w[N], v[N];
int f[M][55];

int main()
{
    int k, m, n;
    scanf("%d%d%d", &k, &m, &n);
    for (int i = 1; i <= n; i++)
        scanf("%d%d", &w[i], &v[i]);

    //初始化
    for (int i = 0; i < M; i++)
        for (int j = 0; j < 55; j++)
            f[i][j] = -1;
    f[0][1] = 0;

    for (int i = 1; i <= n; i++)
    {
        for (int j = m; j >= w[i]; j--)
        {
            int a[55] = {0}, b[55] = {0};
            for (int i = 1; i < 55; i++)
                a[i] = b[i] = -1;
            for (int l = 1; l <= k; l++)
            {
                a[l] = f[j][l];
                // 因为要保证体积刚好为 m
                if (f[j - w[i]][l] != -1)
                    b[l] = f[j - w[i]][l] + v[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++];
            }
        }
    }

    int flag = 1, res = 0;
    for (int i = 1; i <= k; i++)
    {
        res += f[m][i];
        if (f[m][i] == -1)
            flag = 0;
    }
    if (!flag)
        res = 0;

    printf("%d\n", res);

    return 0;
}