题解 P1049 【装箱问题】

帆过—无痕 · 2020-01-01 13:06:42 · 题解

蒟蒻不会用背包，只好用上搜索了\ 嘤嘤嘤\ 对于每件物品，我们只有拿与不拿两种选择\ 于是我们很自然地想到了搜索(好吧其实是我不会用背包)\ 我好菜\ 代码就这样了

#include<bits/stdc++.h>
using namespace std;
int N,M,a[1001],ans;
void dfs(int i,int m){
    if(m>ans)   ans=m;//更新结果 
    for(int j=i+1;j<=N;j++)//真男人绝不回头拿东西!(滑稽)
        if(m+a[j]<=M)//装了还能装！ 
            dfs(j,m+a[j]);//搜索拿地j件物品的情况 
}
int main(){
    cin>>M>>N;
    for(int i=1;i<=N;i++)   cin>>a[i];
    dfs(0,0);//算最多能装多少  
    cout<<M-ans;//用总量减去最多装的 
    return 0;
}

刚写的时候套01背包模板写对了,但还是不太理解思路,于是果断用搜索.还是搜索好啊,只要有思路就好了.这个题的数据好像也不需要记忆化什么的(蒟蒻的最爱哈哈哈)\