题解 P1658 【购物】
顾z
2018-09-02 06:47:58
**题目描述**
你就要去购物了，现在你手上有N种不同面值的硬币，每种硬币有无限多个。为了方便购物，你希望带尽量少的硬币，但要能组合出1到X之间的任意值。
## 广告 [安利博客](https://87960.blog.luogu.org/#)
**分析：**
看到题解做法没有说出原理,所以尝试解释一下.
首先,没有1元面值的硬币肯定无解,因为无法组成1元面值,况且如果我们有1元面值的硬币,那我们就能凑出其他面值(话说带多少硬币去买东西?
然后,我们选择从面值为1元开始凑出所有面值的纸币
(这句话和代码有出入,但是原理相同。)
我们每次选择小于等于当前总面值+1的最大面值的硬币。
//记录**当前总面值为s**
//因为我们此时可以凑出的面值为1~s的钱,我们想要去凑出面值为s+1的情况,所以说我们需要寻找一张面值为s+1的,如果没有,我们的选择将会是最大面值的,再用它(这个面值大的),去和其他面值的拼凑出更大面值.
**概括来讲**
以这个大面值为底,和之前的小面值,是可以凑出更大的面值的钱的.
//可能有点混乱.
以样例为例↓
1 2 5 10
now为当前面值,ans为选取的个数。
now=0,ans=0//此时没有选取
需要寻找面值<=now+1的硬币.
now=1,ans=1//此时选取面值为1的
需要寻找面值<=2的硬币.
now=3,ans=2//此时选取了面值为2的
需要寻找面值<=4的硬币
now=5,ans=3//又选取了面值为2的
需要寻找面值<=6的硬币
now=10,ans=4//选取了面值为5的
需要寻找面值<=11的硬币
now=20,ans=5//选取了面值为10的
这样我们选取的为1·2·2·5·10,是可以凑出1~20的所有情况的。
总之思想就是每次选择的硬币,是可以和前面已经出现过的面值,继续组成更大面值的,每次选择最大面值(满足条件的)的,我们就可以实现我们的贪心。
每一次都要在找到比当前该凑数钱小的最大面值数，这样就可以在钱币数量相同的情况下可拼凑价值最大。------此话[出处](http://www.bubuko.com/infodetail-2621437.html)
--------------------代码---------------------
```cpp
#include<bits/stdc++.h>
#define IL inline
#define RI register int
IL void read(int &x)
{
int f=1;x=0;char s=getchar();
while(s>'9'||s<'0'){if(s=='-')f=-1;s=getchar();}
while(s<='9'&&s>='0'){x=x*10+s-'0';s=getchar();}
x*=f;
}
int x,N,now,ans;
int s[12];
int main()
{
read(x),read(N);
for(RI i=1;i<=N;i++)
read(s[i]);
std::sort(s+1,s+N+1);
if(s[1]!=1)
{
puts("-1");
exit(0);
}
while(now<x)
{
RI i;
for(i=N;i;i--)
if(s[i]<=now+1)break;
ans++;
now+=s[i];
//printf("used:%d\n",s[i]);
}
printf("%d",ans);
}
```