题解 | 装箱问题

#include <bits/stdc++.h>
using namespace std;

int main() {
    int V, n;
    cin >> V;
    cin >> n;
    vector<int> w(n);
    for (int i = 0; i < n; ++i) cin >> w[i];
    // dp[s]：是否能恰好装到体积 s
    vector<char> dp(V + 1, 0);
    dp[0] = 1;
    for (int x : w) {
        if (x > V) continue;                 // 太大直接忽略
        for (int s = V; s >= x; --s)         // 0/1 背包倒序
            if (dp[s - x]) dp[s] = 1;
    }
    int best = 0;
    for (int s = V; s >= 0; --s) if (dp[s]) {
            best = s;
            break;
        }
    cout << (V - best) << '\n';              // 最小剩余空间
    return 0;
}