题解 | [NOIP2001]装箱问题，0-1背包，dp模板

0-1背包的变型

dp[i][j]表示考虑了前i个物品，当背包大小为j的时候，剩余的最少空间。

初始化：

起初一个物品都没有放入，所以dp[0][j] = j；

转移方程：

if (a[i] < j) dp[i][j] = min(dp[i - 1][j], dp[j - a[i]]);

else dp[i][j] = dp[i - 1][j];

节省空间的做法：

因为转移方程只涉及到dp[i]和dp[i - 1]的计算，并且在计算计算第 j 位的结果时，只会依赖于 j 之前的结果。所以可以浓缩为一个维度。在遍历的时候，从右往左遍历，就可以消除第一个维度，进行动态维护。

dp[j] = min(dp[j], dp[j - a[i]]);

其中，j是从大到小遍历。

#include <bits/stdc++.h>
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<int> dp(v + 1, 0);
    
    for (int i = 0; i <= v; i++) 
        dp[i] = i;
    for (int i = 0; i < n; i++) {
        for (int j = v; j >= 0; j--) {
            if (a[i] <= j) {
                dp[j] = min(dp[j], dp[j - a[i]]);
            }
        }
    }
    
    cout << dp[v] << '\n';
}
// 64 位输出请用 printf("%lld")