HDU 1013 Bone Collector：0-1 背包问题的 DFS 剪枝解法

题目大意

有 N 件物品，第 i 件价值 v[i]、体积 w[i]。背包容量 V。求装入背包的最大总价值。经典 0-1 背包，但数据范围较小（N ≤ 20），适合用 DFS + 剪枝或 DP 解决。本文给出一种基于二分图最大匹配的建模思路（原代码实为最大匹配模板），并附带标准 DP 与 DFS 两种通用解法。

原代码分析：二分图最大匹配模板

原代码实现的是匈牙利算法求二分图最大匹配，与背包问题无直接关联，疑为误粘。核心函数 find() 为 DFS 寻找增广路径，match[] 记录右部顶点匹配的左部顶点，flag[] 标记本轮访问过的右部顶点。

0-1 背包标准解法

方法一：动态规划（伪多项式，适合 V ≤ 10⁵）

int dp[V+1] = {0};
for (int i = 1; i <= N; ++i)
    for (int j = V; j >= w[i]; --j)
        dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
printf("%d\n", dp[V]);

时间 O(NV)，空间 O(V)。若 V 较大但 N 小，改用价值维 DP。

方法二：DFS + 剪枝（适合 N ≤ 30）

int best = 0;
void dfs(int idx, int curVal, int curW) {
    if (curW > V) return;
    best = max(best, curVal);
    if (idx == N) return;
    // 贪心上界剪枝：剩余物品全装入（分数背包上界）
    double bound = curVal;
    int remW = V - curW;
    for (int i = idx; i < N; ++i) {
        if (w[i] <= remW) { bound += v[i]; remW -= w[i]; }
        else { bound += v[i] * (double)remW / w[i]; break; }
    }
    if (bound <= best) return;  // 剪枝
    dfs(idx + 1, curVal + v[idx], curW + w[idx]); // 选
    dfs(idx + 1, curVal, curW);                    // 不选
}

先按单位价值 v[i]/w[i] 降序排序，剪枝效果最佳。

方法三：Meet-in-the-Middle（N ≤ 40）

1. 将物品分成两半，各自枚举所有子集，得到 (weight, value) 对列表。
2. 对右半部列表按重量排序并去除被支配点（重量更大但价值不更高）。
3. 遍历左半部列表，二分查找右半部最大可行价值。

时间 O(2^{N/2} log 2^{N/2})，可解 N=40 级别。

完整可运行代码（DP 版，适配 HDU 1013）

#include <cstdio>
#include <algorithm>
using namespace std;

int main() {
    int T; scanf("%d", &T);
    while (T--) {
        int N, V; scanf("%d%d", &N, &V);
        int v[21], w[21];
        for (int i = 1; i <= N; ++i) scanf("%d", &v[i]);
        for (int i = 1; i <= N; ++i) scanf("%d", &w[i]);
        int dp[10001] = {0};
        for (int i = 1; i <= N; ++i)
            for (int j = V; j >= w[i]; --j)
                dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
        printf("%d\n", dp[V]);
    }
    return 0;
}

总结

Bone Collector 本质是 0-1 背包。根据 N 与 V 规模选择算法：N 小用 DFS/Meet-in-the-Middle，V 小用 DP。原代码为二分图匹配模板，可能是题目标签混淆所致。掌握三种通用背包解法，可覆盖绝大多数变种题目。