装箱问题(回溯解法)

chen_z · 2025-02-05 08:56:07 · 题解

解法

这道题明显是 01 背包问题。能否用回溯解决呢？让我们看一看： 0 < n \le 30，用回溯不会超时。我们只需要查看装了当前这个物品后箱子的重量有没有超过箱子的最大容量。如果没有超过，就枚举装这个物品的所有情况，反之不枚举。之后我们再枚举不装这个箱子的所有情况，这个回溯就只差一个最简子问题啦。如果当前要判断的箱子编号大于箱子的个数，就说明我们枚举到最简子问题了。我们更新一下答案再返回即可。

代码

#include<bits/stdc++.h>
using namespace std;
int v,n,a[1000001],ans=1e9;
void dfs(int c,int curw){
    if(c==n+1){
        ans=min(ans,v-curw);
        return;
    }
    if(curw+a[c]<=v){
        dfs(c+1,curw+a[c]);
    }
    dfs(c+1,curw);
    return;
}
int main(){
    cin>>v>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    dfs(1,0);
    cout<<ans;
    return 0;
}