扫二维码与项目经理沟通
我们在微信上24小时期待你的声音
解答本文疑问/技术咨询/运营咨询/技术建议/互联网交流
题目描述：
你就要去购物了，现在你手上有 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元起，快前往官网查看详情吧
我们在微信上24小时期待你的声音
解答本文疑问/技术咨询/运营咨询/技术建议/互联网交流
微信二维码
移动版官网