题解 | [NOIP2001]装箱问题

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

class Solution {
public:
    int minRemainingSpace(int V, vector<int>& volumes) {
        vector<bool> dp(V + 1, false);
        dp[0] = true;
        
        // 对每个物品
        for(int vol : volumes) {
            // 从大到小遍历容量
            for(int j = V; j >= vol; j--) {
                dp[j] = dp[j] || dp[j - vol];
            }
        }
        
        // 找到最大可装体积
        int max_vol = 0;
        for(int i = V; i >= 0; i--) {
            if(dp[i]) {
                max_vol = i;
                break;
            }
        }
        
        return V - max_vol;
    }
};

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

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int V = sc.nextInt();
        int n = sc.nextInt();
        int[] volumes = new int[n];
        for(int i = 0; i < n; i++) {
            volumes[i] = sc.nextInt();
        }
        
        System.out.println(minRemainingSpace(V, volumes));
        sc.close();
    }
    
    public static int minRemainingSpace(int V, int[] volumes) {
        boolean[] dp = new boolean[V + 1];
        dp[0] = true;
        
        // 对每个物品
        for(int vol : volumes) {
            // 从大到小遍历容量
            for(int j = V; j >= vol; j--) {
                dp[j] = dp[j] || dp[j - vol];
            }
        }
        
        // 找到最大可装体积
        int max_vol = 0;
        for(int i = V; i >= 0; i--) {
            if(dp[i]) {
                max_vol = i;
                break;
            }
        }
        
        return V - max_vol;
    }
}

class Solution:
    def min_remaining_space(self, V: int, volumes: list) -> int:
        dp = [False] * (V + 1)
        dp[0] = True
        
        # 对每个物品
        for vol in volumes:
            # 从大到小遍历容量
            for j in range(V, vol - 1, -1):
                dp[j] = dp[j] or dp[j - vol]
        
        # 找到最大可装体积
        max_vol = 0
        for i in range(V, -1, -1):
            if dp[i]:
                max_vol = i
                break
        
        return V - max_vol

# 输入处理
if __name__ == "__main__":
    V = int(input())
    n = int(input())
    volumes = [int(input()) for _ in range(n)]
    
    solution = Solution()
    print(solution.min_remaining_space(V, volumes))