---

P1658 購物

題目鏈接

---

題目描述

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

輸入格式

第一行兩個數X、N，以下N個數，表示每種硬幣的面值。

數據規模

對于30%的數據，滿足N≤3，X≤20;
對于100%的數據，滿足N≤10，X≤1000.

輸出格式

最少需要攜帶的硬幣個數，如果無解輸出-1.

輸入樣例

20 4 1 2 5 10

輸出

5

題意：給定一定面值的錢，讓你能湊夠1-X中的所有值得同時，硬幣數最少

**

思路

**：假設現在的狀態是1~now中的最優情況，若金額再向上遞增的話，會想到2now的級別的最優情況，而又由于貪心的問題，選擇的面值要盡量的大，如果什么也不選的話，那么會得到2now的最優方案，當然會先到中間會有一個較大的面額，到這個面額的時候只需要一張就行了，但是題目的要求是1到n中面額所有取值的最小，所以無關。當時如果我們用一個稍微大一點的面額比如<=now+1,那么我們最大就可達到1到2now+1，比上一個多了一位，但是以此類推，如果我們選用<=now+2的面值，那么我們就會空出now+1的值，因此雖然我們得到了1到2now+2的面值，但是花的票數比原來多了一個1，所以不是最優。

借用大佬的一個例子：

假如now = 8, 那么我就能取到1~8中得所有錢，那么我下一次取的硬幣面值不能超過9；因為假如我取了個10，那么我無法湊9元的。而如果我取了個9， 那么因為我前面能取到1~8中的所有，那么我現在就能取到[1, 8] ∪ 9 ∪ [ (1 + 9) ,(8 + 9) 也就是 [1, 17]; 如果我取了個8， 那么只能湊夠[1, 16];顯而易見是取9更好；所以取不超過(當前總面值數 + 1)的最大值

#include<cstdio> #include<iostream> #include<algorithm> using namespace std; const int maxn=15; int m,n; int a[maxn]; bool flag=0; int main(){cin>>m>>n;for(int i=1;i<=n;i++)cin>>a[i];sort(a+1,a+n+1);if(a[1]==1) flag=1;if(flag==0) cout<<"-1"<<endl;else {int now=0,ans=0;while(now<m){for(int i=n;i>=1;i--){if(a[i]<=now+1) {now+=a[i];ans++;break;}}}cout<<ans<<endl; }return 0; } ``

總結

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

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。