洛谷（P1658购物C++）-创新互联

题目描述：

为饶平等地区用户提供了全套网页设计制作服务，及饶平网站建设行业解决方案。主营业务为成都网站制作、成都网站设计、饶平网站设计，以传统方式定制建设网站，并提供域名空间备案等一条龙服务，秉承以专业、用心的态度为用户提供真诚的服务。我们深信只要达到每一位用户的要求，就会得到认可，从而选择与我们长期合作。这样，我们也可以走得更远！

你就要去购物了，现在你手上有 N种不同面值的硬币，每种硬币有无限多个。为了方便购物，你希望带尽量少的硬币，但要能组合出 1到 X 之间的任意值。

输入格式：

第一行两个数 X, N，以下 N 个数，表示每种硬币的面值。

输出格式：

最少需要携带的硬币个数，如果无解输出 -1。

输入输出样例：

输入：20   4                       输出：5

 1     2      5     10

解题思路：

这道题是一道经典的贪心问题，你得先弄清楚贪心策略

首先，我们必须得有一枚1元面值的硬币，如果没有的话，就是无解，因为你凑不出1元。

下面我们就得列举找规律了（先不按每种面值无限张算，就按每种只有一张算）：

有了面值1元，就一定要有面值2元的，不然你凑不出2元：

目前面值：1元、2元

接着想，需不需要3元呢？其实是不需要的，因为1元和2元可以凑出3元；

目前面值：1元、2元

那四元呢？那就必须要了，无论用前面所有的面值也凑不到4元。

目前面值：1元、2元、4元

五元？可以用1元和4元凑成，不用！  目前面值：1元、2元、4元

六元？可以用2元和4元凑成，不用！  目前面值：1元、2元、4元

七元？可以用1元、2元和4元凑成，不用！  目前面值：1元、2元、4元

八元？前面三个面值怎么也凑不成，必须要用！  目前面值：1元、2元、4元、8元

以此类推会得到这样的数列：1元、2元、4元、8元、16元、32元、64元……

由次我们发现了一个规律：每新来一枚硬币，它的值只可能小于等于前面所有面值和+1

知道了贪心策略，代码就迎刃而解了！

参考代码：

#includeusing namespace std;
int main()
{
	int sum,cnt,n,x,a[1005];//sum表示目前硬币面值总和，cnt表示硬币数 
	cin>>x>>n; 
	for(int i=1;i<=n;i++) cin>>a[i];
	sort(a+1,a+n+1);//从小到大排序，保证小的在前 
	//如果没有一元的硬币，就凑不出1元，所以无解 
	if(a[1]!=1) 
	{
		cout<<"-1"<

我还是一名小学生，程序有点繁琐，希望大家能支持一下！

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧


网站栏目：洛谷（P1658购物C++）-创新互联
文章网址：http://6mz.cn/article/cogsoj.html