【例9.12】完全背包问题

题目描述

设有 $n$ 种物品，每种物品有重量 $W_i$ 和价值 $C_i$ ，每种物品数量无限。背包容量为 $M$ ，从中选取若干件物品（同一种可多次取），使总重量不超过 $M$ 且总价值最大。输入第一行为 $M$ 和 $n$ ，接下来 $n$ 行每行两个整数 $W_i, C_i$ 。输出格式为 max=X。

思路

完全背包：设 $dp[j]$ 表示容量不超过 $j$ 时的最大价值。按物品顺序处理，对第 $i$ 种物品，容量 $j$ 从 $W_i$ 到 $M$ 正序枚举，转移为 $dp[j] = \max(dp[j], dp[j-W_i] + C_i)$ 。正序保证 $dp[j-W_i]$ 已被本轮更新，从而同一种物品可重复选取。初始所有 $dp[j]=0$ ，最终输出 $dp[M]$ 。

参考代码

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
31
32
33
34
35
36#!/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
from itertools import islice


def max_value(items: list[tuple[int, int]], capacity: int) -> int:
    """完全背包：每种物品可取无限多件，返回载重不超过 capacity 时的最大价值。

    best[cap] 表示“前几种物品、容量上限为 cap”时的最大价值。容量正序枚举，使
    best[cap - weight] 读到的是本种物品刚更新过的状态，“再装一件同种物品”因此合法；
    这正是完全背包与 01 背包唯一的实现差别（01 背包必须倒序，保证每种只用一次）。
    """
    best = [0] * (capacity + 1)
    for weight, value in items:
        for cap in range(weight, capacity + 1):
            take = best[cap - weight] + value  # 在本种物品已选若干件的基础上再放一件
            if take > best[cap]:
                best[cap] = take
    return best[capacity]


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    capacity, kind_count = next(data), next(data)          # 题面的 M 与 N
    items = list(islice(zip(data, data), kind_count))       # (重量, 价值) 共 N 种
    print(f"max={max_value(items, 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/**
 * 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
 */
#include <cstdio>

using namespace std;

typedef long long ll;

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

int n, m;              // n 种物品，背包容量 m
int w[MAXN];           // 第 i 种物品的重量
int c[MAXN];           // 第 i 种物品的价值
int dp[MAXM];          // dp[j] 表示容量不超过 j 时的最大价值

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

    // 完全背包：容量正序枚举，允许同一种物品被多次选取
    for (int i = 1; i <= n; i++) {
        for (int j = w[i]; j <= m; j++) {
            if (dp[j - w[i]] + c[i] > dp[j]) {
                dp[j] = dp[j - w[i]] + c[i];
            }
        }
    }

    printf("max=%d\n", dp[m]);
    return 0;
}

【例9.12】完全背包问题

目录

题目描述

思路

参考代码