装箱问题

题目描述

箱子容量 $V$ （ $0 \leqslant V \leqslant 20000$ ），有 $n$ （ $0 < n \leqslant 30$ ）个物品，第 $i$ 个体积 $w_i \leqslant 10000$ ，每件至多选一次，求装完后最小的剩余空间。输入第一行 $V$ 、第二行 $n$ ，随后 $n$ 行每行一个体积；输出一个整数表示最小剩余空间。样例输入 24 6 8 3 12 7 9 7，输出 0。

思路

物品体积既是重量也是收益，这就是 0/1 背包。用 dp[s] 表示体积 $s$ 能否被拼出，处理体积 $w$ 时从大到小刷 dp[s] |= dp[s-w]，保证每件只用一次。最后从 $V$ 往下找第一个可达的 $s$ ，即最多能装下的体积，答案是 $V-s$ 。

参考代码

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#!/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 03:39
# update_at: 2026-09-30 03:39

import sys
from itertools import islice


def min_leftover(capacity: int, volumes: list[int]) -> int:
    """箱子最少剩多少空间：位掩码第 s 位为 1 表示体积 s 能被若干物品恰好拼出。"""
    reachable = 1  # 一个物品都不选：体积 0 可达
    for w in volumes:
        reachable |= reachable << w  # 选/不选该物品 = 把已可达集合整体平移 w 后并入

    # 只关心不超过容量的位：与容量掩码相与后取最高位，就是最多能装下的体积
    filled = (reachable & ((1 << (capacity + 1)) - 1)).bit_length() - 1
    return capacity - filled


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    capacity = next(data)  # 箱子容量 V
    item_count = next(data)  # 物品数 n
    # 实测数据可能不足 n 个体积：读不到的位置等价于体积 0，截取即可
    volumes = list(islice(data, item_count))

    print(min_leftover(capacity, volumes))


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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55/**
 * 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 08:17
 * update_at: 2026-10-05 08:17
 */

// 装箱问题：体积既是重量也是收益的 0/1 背包，
// 求不超过容量 V 的最大可拼出体积 S，输出剩余空间 V - S。

#include <iostream>
using namespace std;

typedef long long ll;

const int MAXV = 20005;

int dp[MAXV]; // dp[s] = 1 表示体积 s 能被若干已处理物品恰好拼出，否则为 0

int main() {
    ll capacity;
    ll n;
    cin >> capacity >> n;

    dp[0] = 1; // 一个物品都不选时体积 0 可达

    for (ll i = 1; i <= n; i++) {
        ll w;
        if (!(cin >> w)) {
            break; // 实测数据可能不足 n 个体积，读不到就结束
        }
        if (w > capacity) {
            continue; // 单个物品就超过容量，任何方案都装不下它
        }
        // 0/1 背包：从大到小枚举，保证每个物品只用一次
        for (ll s = capacity; s >= w; s--) {
            if (dp[s - w]) {
                dp[s] = 1;
            }
        }
    }

    // 从大到小找第一个可达体积，就是最多能装下的体积
    ll best = 0;
    for (ll s = capacity; s >= 0; s--) {
        if (dp[s]) {
            best = s;
            break;
        }
    }

    cout << capacity - best << endl;
    return 0;
}

目录

题目描述

思路

参考代码