题解 P1049 【装箱问题】

· · 题解

我采用的是纯暴力蒟蒻深搜，毕竟没必要动态规划

看看我的dfs三个参数就知道了

这题超级水，直接奉上代码，会在文中注释

#include <iostream>//输入输出流头文件
using namespace std;//懒得在cin、cout前面加std::
int a[20001]/*储存大小*/,v/*三级箱的容量*/,n/*几个东西*/;
int dfs(int nn/*搜索深度记录*/,int m/*从这开始，不能往前搜*/,int s/*被占用空间*/){
    int min=2000000/够小吧，记录最小剩余空间/,t/*临时储存返回的最小空间*/;
    if(nn==1) //搜到底了
    {
        for(int i=m;i<=n;i++) //依次把剩下可用物品累加，凑出最大的
            if(v-s-a[i]>=0&&min>v-s-a[i]) min=v-s-a[i];
    }
    else//事情还没结束 
        for(int i=m;i<=n;i++) //继续遍历~
        {
            if(s+a[i]<=v) t=dfs(nn-1,i+1,s+a[i]);//层层深入
            else continue; //不行，跳过这次
            if(min>t) min=t;//比较
        }
    if(v-s<min) min=v-s;//以防无法进入下一层，min还是2000000
    return min;//返回值
}
int main(){
    cin>>v>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    cout<<dfs(n,1,0)<<endl;
    return 0;//我爱return，return爱我
}

管理员，看我这次鞠躬尽瘁地注释，就过了吧，不要有return个【错误：重复的算法】

我这解法就像这道水题一样水，浪费空间，时间