解题思路

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

  1. 问题分析：

    • 目标：从 个物品中选择若干个，使得总体积不超过 的情况下，尽可能接近
    • 本质：求最接近箱子容量 的物品组合方案
    • 关键点：需要找到所有可能的组合中，不超过 且最接近 的值

  2. 解题步骤：

    • 使用动态规划，类似01背包
    • 表示体积 是否可以被物品组合得到
    • 最后从 往前找到第一个为 的位置，用 减去该值即为答案

  3. 动态规划设计：

    • 状态定义： 表示是否能恰好装满体积
    • 初始化：，其他为
    • 状态转移：

代码

#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))

算法及复杂度

  • 算法：动态规划（01背包变体）
  • 时间复杂度：，其中 是物品数量， 是箱子容量
  • 空间复杂度：，使用一维 数组