P1049装箱问题 23/8/2019

Adis_FireDevil · 2019-08-23 12:40:34 · 题解

这是我这个蒟蒻发布的第二份题解，So—大佬勿喷。

有什么问题可以私信告诉我，大佬们可以给我提一些建议。

好!今天废话不多说,直接给大家解说一场赛马比赛讲解一道dfs题（没错，又是dfs题）

这是我这个蒟蒻发布的第二份题解，So—大佬勿喷。

有什么问题可以私信告诉我，大佬们可以给我提一些建议。

装箱问题的题目因为太容易所以我就不解释了，这道题有两种方法：背包以及dfs(算法标签了解一下),我肯定选dfs啦。

每一个物品考虑装与不装两种情况，最后找出最大值（也就是剩余空间的最小值）即可！

#include<bits/stdc++.h>
using namespace std;
int a[31],ans,n;
int solve(int v,int j){              //v代表箱子目前剩余空间 
    for(int i=j+1;i<=n;i++){
        if(v>=a[i]){
            ans=min(ans,v-a[i]); //记录答案 
            solve(v-a[i],i);     //继续搜索 
        }
    }
}
int main(){
    int v;
    cin>>v>>n;
    ans=v;
    for(int i=1;i<=n;i++)cin>>a[i];
    solve(v,0);
    cout<<ans;
}

—————Adis_FireDevil的第二篇题解 完——————