解题思路:
注意事项:
参考代码:
#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;
}
0.0分
1 人评分