P1049 装箱问题

有一个箱子容量为 V，同时有 n 个物品，每个物品有一个体积。
现在从 n 个物品中，任取若干个装入箱内（也可以不取），使箱子的剩余空间最小。输出这个最小值。

1. 动态规划

使用动态规划计算可达性即可

int maxval(int V,vector<int>&c){
    int n = c.size();
    vector<bool> dp(V+1);
    dp[0] = true;
    int res = 0;
    for(int i=0;i<n;i++)
        for(int j=V;j>=c[i];j--){
            dp[j] = dp[j-c[i]]|dp[j];
            if(dp[j]) res = max(res,j);
        }
    return V-res;
}