Bone Collector

题目解析

就是01背包,直接来

这也是一道非常经典的动态规划 (DP) 题目，它的学名叫做 “0/1 背包问题” (0/1 Knapsack Problem)。

1. 题目分析

问题模型：你有一个容量有限的容器（背包/袋子），面前有一堆物品，每个物品都有自己的体积（消耗的成本）和价值（获得的收益）。
规则：对于每一个骨头，你只有两种选择：
1. 拿走 (1)：占用背包体积，获得价值。
2. 不拿 (0)：不占用体积，没有价值。
  
  （注：不能把骨头切开拿一半，也不能重复拿同一个骨头，这就是为什么叫 “0/1” 背包）。
目标：在不超过背包总容量 $V$ 的前提下，让装入的骨头总价值最大。

2. 核心思路

如果要用暴力枚举（拿或不拿），复杂度是 $2^N$ 。当 $N=1000$ 时，这个数字大得宇宙都装不下。所以必须用动态规划。

我们定义一个数组 dp。

$dp[j]$ 的含义是：当背包容量为 $j$ 时，能获得的最大价值。

状态转移方程

当我们面对第 $i$ 块骨头时（设它的体积是 $c$ ，价值是 $w$ ），对于当前的容量 $j$ ，我们怎么选？

dp[j] = \max(dp[j], \quad dp[j - c] + w)

这个公式的意思是：

$dp[j]$ (不拿)：我不拿这块骨头，那么最大价值就维持之前的状态，即容量为 $j$ 时的旧值。
$dp[j - c] + w$ (拿)：我决定拿这块骨头。前提是我必须给它腾出 $c$ 的空间。那么我就要找“容量为 $j-c$ 时的最大价值”，加上当前这块骨头的价值 $w$ 。
$\max$ ：在这两种选择中，谁大我就选谁。

3. 关键技巧：一维数组优化

为了节省空间，我们通常使用一维数组。但在使用一维数组解决 0/1 背包问题时，内层循环必须从大到小（倒序）遍历。

为什么要倒序？

如果从小到大遍历（例如 $j$ 从 $c$ 到 $V$ ），当我们计算 $dp[j]$ 时，用到的 $dp[j-c]$ 可能已经是“放入了当前物品”之后的新值了。这就导致一个物品被放入了多次（变成了“完全背包问题”）。

倒序遍历（ $j$ 从 $V$ 到 $c$ ）能保证我们在计算 $dp[j]$ 时，引用到的 $dp[j-c]$ 还是上一轮（即没放当前物品前）的状态。

4. 代码实现 (C++)

注意：题目输入中，第二行是价值，第三行是体积。写代码时读取顺序不要搞反。

cpp

#include <iostream>
#include <vector>
#include <cstring> // for memset
#include <algorithm> // for max

using namespace std;

// 全局变量定义，N和V最大为1000
const int MAXV = 1005; 
int dp[MAXV]; 
int values[MAXV];
int volumes[MAXV];

void solve() {
    int N, V;
    cin >> N >> V;

    // 清空 DP 数组，因为有多个测试用例
    // 将 dp 数组全部初始化为 0
    memset(dp, 0, sizeof(dp));

    // 读取价值 (题目说第二行是价值)
    for (int i = 1; i <= N; ++i) {
        cin >> values[i];
    }

    // 读取体积 (题目说第三行是体积)
    for (int i = 1; i <= N; ++i) {
        cin >> volumes[i];
    }

    // 核心算法：0/1 背包
    for (int i = 1; i <= N; ++i) { // 遍历每一个骨头
        // 必须倒序遍历容量！从 V 到 volumes[i]
        for (int j = V; j >= volumes[i]; --j) {
            dp[j] = max(dp[j], dp[j - volumes[i]] + values[i]);
        }
    }

    cout << dp[V] << endl;
}

int main() {
    // 优化输入输出
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int T;
    cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}

5. 样例推演 (Dry Run)

输入：

Plaintext

N=5, V=10
价值: 1 2 3 4 5
体积: 5 4 3 2 1

初始状态：dp 数组全是 0。

骨头1 (体积5, 价值1):
- $j$ 从 10 到 5，dp[j] 更新为 $\max(0, 0+1) = 1$ 。
- dp 变成: [0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1] (下标0-10)
骨头2 (体积4, 价值2):
- $j=10$ : $\max(dp[10], dp[6]+2) \to \max(1, 1+2) = 3$
- …
- $j=9$ : $\max(1, 1+2) = 3$
- $j=4$ : $\max(0, 0+2) = 2$
- 现在 dp 中较大的容量位置已经开始累积价值。
骨头3 (体积3, 价值3):
- $j=10$ : $\max(3, dp[7]+3)$ . 此时 $dp[7]$ 还是 1 (骨头1的贡献)。所以 $1+3=4$ 。
- …这里继续更新。

…快进到最后…

我们可以直观地看：要凑出体积 $\le 10$ ，怎么拿价值最大？

观察数据：体积越小，价值反而越高（反直觉的骨头）。

拿骨头5 (体积1, 价值5)
拿骨头4 (体积2, 价值4)
拿骨头3 (体积3, 价值3)
拿骨头2 (体积4, 价值2)

总体积 = $1+2+3+4 = 10$ 。

总价值 = $5+4+3+2 = 14$ 。

程序输出 14。

总结

这道题是 背包问题 家族中最基础的成员。

要点 1：状态定义 $dp[j]$ 表示容量为 $j$ 时的最大价值。
要点 2：一维数组优化时，内层循环从大到小。
要点 3：多组测试数据 ( $T$ 组)，每次记得初始化/清空数组。

目录