题解 | #装箱问题#

#include <iostream>
using namespace std;
const int N = 2*1e4+10;
int dp[N];  //dp[k]表示容量为v时，最大能装多大体积的物品
int nums[31];
int main() {
    int v,n;
    scanf("%d", &v);
    scanf("%d", &n);
    for(int i = 1; i <= n; i++){
        scanf("%d", &nums[i]);
    }
    for(int i = 1; i<=n;i++){
        for(int j = v; j >= 0; j--){
            if(j>=nums[i]){
                dp[j] = max(dp[j], dp[j-nums[i]]+nums[i]);
            }
        }
    }
    printf("%d", v-dp[v]);
    return 0;
}
// 64 位输出请用 printf("%lld")