【例9.11】01背包问题

题目描述

一个旅行者有一个最多能装 $M$ 公斤的背包，现在有 $N$ 件物品，第 $i$ 件物品重量为 $W_i$ 、价值为 $C_i$ ，每件物品最多选一次，求能获得的最大总价值。输入：第一行两个整数 $M$ （背包容量， $M \leqslant 200$ ）和 $N$ （物品数量， $N \leqslant 30$ ）；接下来 $N$ 行每行两个整数 $W_i, C_i$ ，表示每件物品的重量和价值。输出：仅一行，一个数，表示最大总价值。 样例输入：10 4，2 1，3 3，4 5，7 9（每行一项）；样例输出：12（选物品 2 和 4，重量 $3+7=10$ ，价值 $3+9=12$ ）

思路

一维 0/1 背包： $dp[v]$ 表示容量不超过 $v$ 时的最大价值，逐件物品转移 $dp[v] = \max(dp[v], dp[v-W_i]+C_i)$ ，答案为 $dp[M]$ 。内层容量必须倒序扫描，这样 $dp[v-W_i]$ 读到的还是没考虑本物品的旧值，保证每件物品最多选一次（正序就变成完全背包）。 $dp$ 全初始化为 $0$ 即可，因为"一件不拿"总是合法方案。

参考代码

Python 版：

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-09-30 02:38
# update_at: 2026-09-30 02:38

import sys


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    capacity, count = next(data), next(data)  # 题面的 M 与 N
    items = [(next(data), next(data)) for _ in range(count)]  # 每件的 (W_i, C_i)

    # dp[v] = 已处理物品中，总重量不超过 v 时的最大价值；不要求装满，故初值全 0
    dp = [0] * (capacity + 1)

    for weight, value in items:
        # 容量必须倒序扫描：读到的 dp[v - weight] 还是"没考虑本物品"的旧值，
        # 本物品至多被选一次（正序会读到本轮刚更新的值，那就成了完全背包）。
        # weight > capacity 时 range 为空，装不下的物品自动被跳过。
        for v in range(capacity, weight - 1, -1):
            dp[v] = max(dp[v], dp[v - weight] + value)

    print(dp[capacity])


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-05 07:39
 * update_at: 2026-10-05 07:39
 */

// 01 背包：一维滚动数组，容量倒序扫描保证每件物品最多选一次。
#include <iostream>
#include <algorithm>
using namespace std;

typedef long long ll;

const int MAXN = 35;    // 物品数上限
const int MAXM = 205;   // 背包容量上限

ll m, n;                // 背包容量、物品数量
ll w[MAXN], c[MAXN];    // w[i] 第 i 件物品重量，c[i] 第 i 件物品价值
ll dp[MAXM];            // dp[v]：容量不超过 v 时能获得的最大价值

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> m >> n;
    for (int i = 1; i <= n; i++)
        cin >> w[i] >> c[i];

    // 转移：dp[v] = max(dp[v], dp[v-w]+c)，v 必须从大到小扫描。
    // 倒序时 dp[v-w] 还没被本轮更新，是"没考虑本物品"的旧值；
    // 正序会让同一件物品被反复装入，变成完全背包。
    for (int i = 1; i <= n; i++)
        for (int v = (int)m; v >= (int)w[i]; v--)
            dp[v] = max(dp[v], dp[v - w[i]] + c[i]);

    cout << dp[m] << endl;
    return 0;
}