題目描述
你就要去購物了，現(xiàn)在你手上有N種不同面值的硬幣，每種硬幣有無限多個。為了方便購物，你希望帶盡量少的硬幣，但要能組合出1到X之間的任意值。

輸入輸出格式

輸入格式：
第一行兩個數(shù)X、N，以下N個數(shù)，表示每種硬幣的面值。

【數(shù)據(jù)規(guī)模】
對于30%的數(shù)據(jù)，滿足N≤3，X≤20;
對于100%的數(shù)據(jù)，滿足N≤10，X≤1000.

輸出格式：
最少需要攜帶的硬幣個數(shù)，如果無解輸出-1.

輸入輸出樣例

輸入樣例#1：
20 4
1 2 5 10
輸出樣例#1：
5
.
.
.
.
.
.

分析

正解是貪心，每次拿當(dāng)前能拿的最大的一個，這樣算出來總數(shù)肯定是最少的。
.
.
.
.
.
.

程序：

#include<iostream> #include<algorithm> using namespace std; int n,x,s[1005]; int main() { cin>>x>>n; int i,j,sum=0,ans=0; for(i=1;i<=n;i++)cin>>s[i]; sort(s+1,s+1+n); if(s[1]!=1){ cout<<-1; return 0; } while(true){ if(sum>=x){ cout<<ans;return 0; } for(i=n;i>=1;i--) if(s[i]<=sum+1){sum+=s[i];ans++;break;} } return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/YYC-0304/p/9499974.html

總結(jié)

以上是生活随笔為你收集整理的购物的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。