要用掉数量最多的硬币，则要尽量用面额小的硬币。
从面额最小的硬币开始凑起，上限为有的硬币数或付清P所需最大硬币数。
下限为 0 或上限减去（25/当前硬币面额），意为若用之后的面额的硬币凑不出某一数值，则必然也凑不出该数值加25。命题在该数值大于当前面额时成立。
确定上下限后，对每种面额搜索。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| #include<bits/stdc++.h>
using namespace std;
int p,v[4]={1,5,10,25},n[4];
int dfs(int i,int sum,int ans)
{
if (sum==p) return ans;
if (i==4) return -1;
int high=min((p-sum)/v[i],n[i]),low=max(0,high-25/v[i]);
for(int j=high;j>=low;j--)
{
int tem=dfs(i+1,sum+j*v[i],ans+j);
if(tem!=-1) return tem;
}
return -1;
}
int main()
{
cin>>p;
for(int i=0;i<4;i++) cin>>n[i];
int ans=dfs(0,0,0);
if(ans==-1) cout<<"Impossible";
else cout<<ans;
}
|
参考https://blog.csdn.net/wwwlps/article/details/93122197
