【正经题解】装箱问题

使用动态规划来求解问题。 $a$ 数组存储每个物品的体积， $f$ 数组存储动态规划的结果。通过两重循环，逐步更新 $f$ 数组，最终 得到最小的剩余空间。最后，输出箱子的最小空间。

#include<iostream>
using namespace std;

int a[20010];  // 存储每个物品的体积
int f[20010];  // 存储动态规划的结果

int main(){
    int x, n;
    cin >> x >> n;  // 输入箱子容量和物品数量
    for(int i = 1; i <= n; i++){
        cin >> a[i];  // 输入每个物品的体积
    }

    for(int i = 1; i <= n; i++){
        for(int j = x; j >= 1; j--){
            if(j >= a[i]){
                f[j] = max(f[j], f[j - a[i]] + a[i]);  // 动态规划更新结果
            }
        }
    }

    cout << x - f[x] << endl;  // 输出最小空间
    return 0;
}