P1049 [NOIP 2001 普及组] 装箱问题

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

int main() {
    int V, n;
    cin >> V >> n;
    vector<int> a(n);
    for (int &x : a) cin >> x;

    // dp[j] = 箱子容量为 j 时，最多能装下的总体积。
    // 初始全 0：什么都不装时能装下 0。
    vector<int> dp(V + 1, 0);

    for (int i = 0; i < n; i++) {
        // 倒着枚举容量：这样用到的 dp[j-a[i]] 还是「没放这个物品」时的值，
        // 每个物品最多只会被装一次，这就是 0/1 背包。
        for (int j = V; j >= a[i]; j--) {
            dp[j] = max(dp[j], dp[j - a[i]] + a[i]);
        }
    }

    // 装得越满，剩余空间越小
    cout << V - dp[V] << "\n";
    return 0;
}