题解 | 装箱问题

装箱问题

https://www.nowcoder.com/practice/c990bd0bf8e04bfbb19c0964401c8f77

解题思路

这是一个01背包问题的变体：

问题分析：
- 目标：从 $n$ 个物品中选择若干个，使得总体积不超过 $V$ 的情况下，尽可能接近 $V$
- 本质：求最接近箱子容量 $V$ 的物品组合方案
- 关键点：需要找到所有可能的组合中，不超过 $V$ 且最接近 $V$ 的值
解题步骤：
- 使用动态规划，类似01背包
- $dp[j]$ 表示体积 $j$ 是否可以被物品组合得到
- 最后从 $V$ 往前找到第一个为 $true$ 的位置，用 $V$ 减去该值即为答案
动态规划设计：
- 状态定义： $dp[j]$ 表示是否能恰好装满体积 $j$
- 初始化： $dp[0] = true$ ，其他为 $false$
- 状态转移： $dp[j] = dp[j] || dp[j-num]$

代码

c++
java
python

#include <iostream>
#include <vector>
using namespace std;

int minRemainingSpace(int V, vector<int>& nums) {
    vector<bool> dp(V + 1, false);
    dp[0] = true;
    
    // 对每个物品进行01背包
    for(int num : nums) {
        for(int j = V; j >= num; j--) {
            dp[j] = dp[j] || dp[j - num];
        }
    }
    
    // 从V往前找到第一个可以达到的体积
    for(int j = V; j >= 0; j--) {
        if(dp[j]) {
            return V - j;
        }
    }
    return V;
}

int main() {
    int V, n;
    cin >> V >> n;
    vector<int> nums(n);
    for(int i = 0; i < n; i++) {
        cin >> nums[i];
    }
    cout << minRemainingSpace(V, nums) << endl;
    return 0;
}

import java.util.*;

public class Main {
    public static int minRemainingSpace(int V, int[] nums) {
        boolean[] dp = new boolean[V + 1];
        dp[0] = true;
        
        // 对每个物品进行01背包
        for(int num : nums) {
            for(int j = V; j >= num; j--) {
                dp[j] = dp[j] || dp[j - num];
            }
        }
        
        // 从V往前找到第一个可以达到的体积
        for(int j = V; j >= 0; j--) {
            if(dp[j]) {
                return V - j;
            }
        }
        return V;
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int V = sc.nextInt();
        int n = sc.nextInt();
        int[] nums = new int[n];
        for(int i = 0; i < n; i++) {
            nums[i] = sc.nextInt();
        }
        System.out.println(minRemainingSpace(V, nums));
        sc.close();
    }
}

def min_remaining_space(V: int, nums: list) -> int:
    dp = [False] * (V + 1)
    dp[0] = True
    
    # 对每个物品进行01背包
    for num in nums:
        for j in range(V, num - 1, -1):
            dp[j] = dp[j] or dp[j - num]
    
    # 从V往前找到第一个可以达到的体积
    for j in range(V, -1, -1):
        if dp[j]:
            return V - j
    return V

if __name__ == "__main__":
    V = int(input())
    n = int(input())
    nums = [int(input()) for _ in range(n)]
    print(min_remaining_space(V, nums))