P1049 装箱问题

calendar May 5, 2026 · 4 分钟阅读 · 动态规划 背包问题  ·
分享到: linkedin copy

文章目录

题目信息

字段 内容
题号 P1049
难度 橙题（普及-）
知识点 0-1 背包、动态规划

题目描述

有一个容量为 m 的箱子（单位：立方米），现有 n 件物品，物品 i 的体积正好等于它的价值 v_i。

将物品装入箱子，要求每件物品要么装进去、要么不装（不能拆开装一半）。问如何装载才能使箱子的剩余空间最小？输出最小的剩余空间。

输入格式：

  • 第一行两个整数 m 和 n（1 ≤ m ≤ 20000，1 ≤ n ≤ 30）
  • 第二行 n 个整数，表示每件物品的体积（等于价值）

输出格式：一个整数，表示箱子最小的剩余空间。

解题思路

核心思想

本题是 0-1 背包问题的经典变种。

普通 0-1 背包中，物品有权重（体积）和价值，两个可以不同。但本题中，每件物品的体积等于价值（v_i = weight_i = value_i）。

这意味着：装进去的物品总体积越大，箱子剩余空间越小。所以问题转化为——

在容量 m 的背包中，选择若干物品使总体积尽可能接近 m，即求最大可装载体积 f[m]，答案就是 m - f[m]。

状态定义

f[j]：考虑前 i 件物品（处理过程中逐步加入），容量为 j 的箱子能装下的最大总体积。

状态转移

f[j] = max(f[j], f[j - v[i]] + v[i]);
  • 不选第 i 件物品：保持原来的 f[j]
  • 选第 i 件物品：前提是 j >= v[i]，即箱子还装得下。把第 i 件物品的体积 v[i] 加进去，加上在剩余容量 j - v[i] 中能装的最大体积 f[j - v[i]]

最终答案

cout << m - f[m];

f[m] 是容量为 m 的箱子能装下的最大总体积，两者相减即为最小剩余空间。

为什么内层循环要倒序？

这是 0-1 背包的关键点。数组 f 是原地更新的：

  • f[j - v[i]] 在正序时已经被当前第 i 件物品更新过了，相当于同一件物品被选了多次（完全背包）
  • 倒序遍历确保 f[j - v[i]] 来自上一轮（即第 i-1 件物品）的状态，每件物品最多只选一次
for (int i = 1; i <= n; i++) {
    for (int j = m; j >= v[i]; j--) {   // 倒序！
        f[j] = max(f[j], f[j - v[i]] + v[i]);
    }
}

完整代码

C++

#include <iostream>

using namespace std;

// 箱子最大容量 20000
const int kMaxCapacity = 20000;

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

    int m, n;
    cin >> m >> n;

    int v[31];
    for (int i = 1; i <= n; i++) {
        cin >> v[i];
    }

    // f[j]: 容量为 j 的箱子能装下的最大总体积
    int f[kMaxCapacity + 1] = {0};

    for (int i = 1; i <= n; i++) {
        for (int j = m; j >= v[i]; j--) {
            f[j] = max(f[j], f[j - v[i]] + v[i]);
        }
    }

    cout << m - f[m] << "\n";
    return 0;
}

关键代码讲解

1. 状态转移方程

f[j] = max(f[j], f[j - v[i]] + v[i]);

这行代码体现了 0-1 背包的核心选择逻辑：要么不选第 i 件（f[j] 保持），要么选它（f[j - v[i]] + v[i]）。

2. 倒序遍历

for (int j = m; j >= v[i]; j--)

从 m 倒着往 v[i] 遍历，确保每件物品只被选择一次。如果正序写 for (j = v[i]; j <= m; j++)，就是完全背包了——本题要求每件物品最多选一次，所以必须倒序。

3. 答案计算

cout << m - f[m];

f[m] 是 DP 结束后，容量为 m 的箱子能装的最大体积。用总容量减去已装体积，就是剩余空间。

复杂度分析

方法 时间复杂度 空间复杂度
0-1 背包 DP O(n × m) O(m)

n ≤ 30，m ≤ 20000，最多约 60 万次操作，轻松通过。

易错点

  1. 内层循环必须倒序：正序会导致同一物品被多次选择，变成完全背包而非 0-1 背包
  2. 数组下界：f 的大小应至少为 m + 1，且 j >= v[i] 是循环下界，防止数组越界
  3. 变量命名：m 是箱子容量，n 是物品数量，v[i] 是体积，不要混淆

其他语言解法

Python

"""P1049 装箱问题 - Python 实现"""
import sys
from typing import List


def solve() -> None:
    """0-1 背包变形：体积=价值，求最小剩余空间"""
    # 一次性读完全部输入，兼容 n 个整数跨多行的情况
    data: List[str] = sys.stdin.read().split()
    m, n = int(data[0]), int(data[1])
    v: List[int] = [0] + [int(x) for x in data[2:2 + n]]  # 下标从 1 开始

    f = [0] * (m + 1)

    for i in range(1, n + 1):
        # 倒序遍历，保证每件物品只选一次
        for j in range(m, v[i] - 1, -1):
            f[j] = max(f[j], f[j - v[i]] + v[i])

    print(m - f[m])


if __name__ == '__main__':
    solve()

Java

import java.io.BufferedInputStream;
import java.io.IOException;
import java.io.PrintWriter;

/**
 * P1049 装箱问题
 * 洛谷强制要求类名为 Main，禁止使用 Scanner（会 MLE）
 */
public class Main {
    private static final int kMaxCapacity = 20000;

    public static void main(String[] args) throws IOException {
        BufferedInputStream bis = new BufferedInputStream(System.in);
        PrintWriter pw = new PrintWriter(System.out);

        int m = readInt(bis);
        int n = readInt(bis);

        int[] v = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            v[i] = readInt(bis);
        }

        int[] f = new int[m + 1];

        for (int i = 1; i <= n; i++) {
            for (int j = m; j >= v[i]; j--) {
                f[j] = Math.max(f[j], f[j - v[i]] + v[i]);
            }
        }

        pw.println(m - f[m]);
        pw.flush();
    }

    private static int readInt(BufferedInputStream bis) throws IOException {
        int result = 0;
        int c;
        do {
            c = bis.read();
        } while (c != -1 && c <= ' ');
        while (c >= '0' && c <= '9') {
            result = result * 10 + (c - '0');
            c = bis.read();
        }
        return result;
    }
}

Go

package main

import (
	"bufio"
	"fmt"
	"os"
)

const kMaxCapacity = 20000

func main() {
	in := bufio.NewReader(os.Stdin)

	var m, n int
	fmt.Fscan(in, &m, &n)

	v := make([]int, n+1)
	for i := 1; i <= n; i++ {
		fmt.Fscan(in, &v[i])
	}

	f := make([]int, m+1)

	for i := 1; i <= n; i++ {
		for j := m; j >= v[i]; j-- {
			if f[j-v[i]]+v[i] > f[j] {
				f[j] = f[j-v[i]] + v[i]
			}
		}
	}

	fmt.Println(m - f[m])
}

JavaScript

'use strict';

/**
 * P1049 装箱问题 - 0-1 背包变形
 * @param {number} capacity - 箱子容量 m
 * @param {number} n - 物品数量
 * @param {number[]} volumes - 各物品体积（体积=价值），下标从 1 开始
 * @returns {number} 最小剩余空间
 */
function minWasteSpace(capacity, n, volumes) {
    const f = new Array(capacity + 1).fill(0);

    for (let i = 1; i <= n; i++) {
        // 倒序遍历，防止同一物品被重复选择
        for (let j = capacity; j >= volumes[i]; j--) {
            f[j] = Math.max(f[j], f[j - volumes[i]] + volumes[i]);
        }
    }

    return capacity - f[capacity];
}

function main() {
    const input = require('fs').readFileSync('/dev/stdin', 'utf8');
    const tokens = input.trim().split(/\s+/).map(Number);
    const m = tokens[0];
    const n = tokens[1];
    const v = [0, ...tokens.slice(2)];  // 下标从 1 开始

    console.log(minWasteSpace(m, n, v));
}

main();