易懂带注释题解

这道题属于子集枚举的典型例题。对于每个物品有两种做法：选与不选，所以需要用递归枚举。递归每一层枚举选和不选的情况，顺带算好当前物品体积之和。如果n个物品枚举完，则将此次剩余空间值与最小剩余值进行对比，反复更新。

#include<bits/stdc++.h>
using namespace std;
int v, n, a[32], ans, sum;
void dfs(int k){
    if(k == n + 1){//n个物品已枚举结束
        ans = min(ans, v - sum);//更新最小剩余空间值
        return;
    }
    if(sum + a[k] <= v){//还能装下
        sum += a[k];
        dfs(k + 1);//进行下一物品枚举
        sum -= a[k];//已枚举出一轮结果，回溯
    }
    dfs(k + 1);//装不下，直接递归到最后一层
}
int main(){
    cin >> v >> n;
    for(int i = 1; i <= n; i++){
        cin >> a[i];
    }
    ans = v;//记录剩余空间值
    dfs(1);
    cout << ans;
    return 0;
}