蓝桥杯算法提高VIP-贪吃的大嘴 DFS+剪枝 很好理解

解题思路:

注意事项:

参考代码:

#include<iostream>
#include<algorithm>
using namespace std;
struct cake{
    int m,n;
}ca[55];
bool cmp(cake c1,cake c2){
    return c1.m>c2.m;
}
int t,n;
int minx = 10000007;
void dfs(int s,int x,int sum){
    if(sum>t){
        return;
    }
    if(x>=minx){
        return;
    }
    if(sum == t){
        minx = min(minx,x);
        return ;
    }
    for(int i=s;i<n;i++){
        int l = ca[i].n;
        for(int j=1;j<=l;j++){
            ca[i].n -= j;
            dfs(s+1,x+j,sum+ca[i].m*j);
            ca[i].n += j;
        }
    }
}
int main(){
    cin>>t>>n;
    int a,b;
    for(int i=1;i<=n;i++){
        cin>>a>>b;
        ca[i-1].m = a;
        ca[i-1].n = b;
    }
    sort(ca,ca+n,cmp);
    dfs(0,0,0);
    if(minx==10000007)
        cout<<"><";
    else
        cout<<minx;
    return 0;
}