题解 | 装箱问题

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

int main() {
    int V, n;
    cin >> V >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];

    vector<bool> dp(V + 1, false); // dp[j]: 容量为j是否可以被填满
    dp[0] = true;

    for (int i = 0; i < n; i++) {
        for (int j = V; j >= a[i]; j--) {
            if (dp[j - a[i]]) dp[j] = true;
        }
    }

    // 从大到小找最大能装的体积
    for (int j = V; j >= 0; j--) {
        if (dp[j]) {
            cout << V - j << endl; // 箱子剩余空间 = 总容量 - 已装体积
            break;
        }
    }

    return 0;
}