HDU-3033 I love sneakers! 题解

题目大意

有 n 个物品，分成了 k 组，每个物品有体积和价值，把 n 个物品放到容量为 V 的背包中，保证每组至少放一件，求能获得的最大价值，如果不能实现，输出“Impossible”。

样例

样例输入 1

样例输出 1

样例 1 说明

选取物品 1，2，3，4 能够获得最大价值。

分析

标准的分组背包是每组最多选一个，这次变成了每组至少选一个。
- 最开始想到了一半，既然是每组至少选一个，每组中每个物品都从上一组转移过来就行了，但是很显然，组内的物品叠加无法实现，后来没有继续想，果断放弃了，尴尬不已。
- 后来又想，每组中尝试先限定本组中第 i 个物品选择，再用把其他物品跑 01 背包，但是最后选取决策不知道该怎么办了，还是放弃吧。
其实按照第一条思路接着往下走，答案就出来，针对每组中的物品，每个物品放与不放，既要考虑从前 i-1 组的状态考虑转移过来，也要考虑本组中若干物品的叠加，所以也要对比从本组中前面的物体的放置情况转移。
而且，同时要保证本组中的物品至少放一件，也就是至少要保证有一个物品是从前 i-1 组中转移过来。
因此，对比以前写的背包，如果不放该物品，可以把上面的状态直接拿过来，但是这道题就不适用了，否则可能会出现某组中一件物品都不放的情况。
首先是初始化的问题：
- 网上给出的题解好多都是要把所有值初始化成 -1，而把第 0 行初始化成 0，有些解释并不正确。要看数据范围，物品的体积和价值都是从 0 开始的（这也是比较坑的地方，直接导致我后面的转移方程出现问题）。经过尝试，全部初始化成 0 也可以，因为数据不存在价值全部为 0 的情况，否则就没办法确定 “Impossible” 的情况了，感觉应该加一组。当然，初始化的时候也可以只把 dp[0][0] 初始化成 0，其他为 -1，这样最后求得的是恰好装满时候的最大价值，最后需要搜一遍最大值（参考第二个代码）。
定义 dp[i][j] 表示前 i 组物品放到容量为 j 的背包中所得的最大价值。之后是跑背包了，外层循环每组，由于每组可以放多件，所以有点 01 背包的感觉了，物品之间没有制约，因此第二层跑组内物品（如果放在最内层不能实现组内多件物品叠加的情况）。按照前面的数组定义，内层容量的循环应该采用倒序（因为每件物品不会重复选择，结合后面的转移方程更好理解）。
- 转移方程有两部分：
  1. 如果当前组中选过物品了，则看看在此基础上能否再加一件物品 k：\(f[i][j] = max \{f[i][j], f[i][j-cost[k]]+val[k]\}\)。但是怎么知道该组有没有放过物品了呢？看初始化，如果 \(f[i][j-cost[k]] == -1\) 就可以肯定，没有方案能实现容量为 j 的情况，否则，可以肯定 \(f[i][j-cost[k]]\) 是已经装过该组中的某些物品使得它不等于 -1 了。
  2. 当然物品 k 还可以看作是该组中的第一件装入背包中的，因此，可以从前 i-1 组的状态转移：\(f[i][j] = max \{f[i][j], f[i-1][j-cost[k]]+val[k]\}\)。当然，前提也得保证 \(f[i-1][j-cost[k]]\) 是有效的，即不等于 -1。含义跟第一个解释类似。
  3. 最困扰我的一个问题，就是这两个式子能否调换一下位置？当然这么说，肯定是不行。这个问题折腾了我一整天，不知道为什么网上给的题解都是清一色按照上面的这个顺序写的，而且没有说明为什么……都要郁闷死了。最后才发现问题所在，还是先要看数据范围，每个物品的体积和价值最小为 0，这个就比较尴尬了。如果某个物品的体积为 0，但是价值大于 0，那么按照上面的顺序不会出现问题；但是如果调换顺序后，则会出现该物品为重复放进去的问题，因为 \(j-cost[k] = j\)，从上一组转移过来，又从本组中转移过来……WA的爽歪歪。
最后是求解
- 这个应该不用多说了，按照上面的初始化，最后输出最后的元素即为所求。
- 如果初始化的时候只把 dp[0][0] 初始化为 0，那么最后求解的时候要循环找一下最大值，因为这时候 dp 存的值为恰好装满的时候结果，自己思考一下，想想转移过程，不难理解。

代码 1（第 0 行为 0，其他为 -1）

// 由于我写法比较麻烦，所有的鞋存在了结果体数组 shoes 中
// 分组信息存在了二维数组 a 中
void solve() {
    memset(dp, -1, sizeof(dp));
    memset(dp[0], 0, sizeof(dp[0]));

    for (int i = 1; i <= kind; ++i) {
        for (int k = 1; k <= a[i][0]; ++k) {
            const Node &p = shoes[a[i][k]];
            for (int j = money; j >= p.price; --j) {
                if (dp[i][j-p.price] != -1) { // 该值不等于-1，意味着之前装过该组物品，可以直接考虑在此基础上直接装一件
                    dp[i][j] = max(dp[i][j], dp[i][j-p.price]+p.val);
                }
                if (dp[i-1][j-p.price] != -1) { // 说明当前容量可以再买鞋p
                    dp[i][j] = max(dp[i][j], dp[i-1][j-p.price]+p.val);
                }
            }
        }
    }

    if (dp[kind][money] == -1) {
        printf("Impossible\n");
    } else {
        printf("%d\n", dp[kind][money]);
    }
}

代码 2（只初始化 dp[0][0]）

// 由于我写法比较麻烦，所有的鞋存在了结果体数组 shoes 中
// 分组信息存在了二维数组 a 中
void solve() {
    memset(dp, -1, sizeof(dp));
    dp[0][0] = 0;

    for (int i = 1; i <= kind; ++i) {
        for (int k = 1; k <= a[i][0]; ++k) {
            const Node &p = shoes[a[i][k]];
            for (int j = money; j >= p.price; --j) {
                if (dp[i][j-p.price] != -1) { // 该值不等于-1，意味着之前装过该组物品，可以直接考虑在此基础上直接装一件
                    dp[i][j] = max(dp[i][j], dp[i][j-p.price]+p.val);
                }
                if (dp[i-1][j-p.price] != -1) { // 该物品作为此组第一件被装入时价值是否更优
                    dp[i][j] = max(dp[i][j], dp[i-1][j-p.price]+p.val);
                }
            }
        }
    }
    int ans = -1;
    for (int i = money; i > 0; --i) {
        ans = max(ans, dp[kind][i]);
    }
    if (ans == -1) {
        printf("Impossible\n");
    } else {
        printf("%d\n", ans);
    }
}

代码 3（全部初始化为 0，这种智能针对数据中的疏漏了，但是可以参考）

void solve() {
    memset(dp, 0, sizeof(dp));

    for (int i = 1; i <= kind; ++i) {
        for (int k = 1; k <= a[i][0]; ++k) {
            const Node &p = shoes[a[i][k]];
            for (int j = money; j >= p.price; --j) {
                dp[i][j] = max(dp[i][j], dp[i][j-p.price]+p.val);
                dp[i][j] = max(dp[i][j], dp[i-1][j-p.price]+p.val);
            }
        }
    }

    if (dp[kind][money] == 0) {
        printf("Impossible\n");
    } else {
        printf("%d\n", dp[kind][money]);
    }
}