louisfghbvc的部落格

題目連結:   https://e-tutor.itsa.org.tw/e-Tutor/mod/programming/view.php?id=3644

題目大意:  給你x元，給你n種硬幣，問說買方+賣方使用最少硬幣數

思路:  貪心 or 動態規劃。先說動態規劃，首先建立一個表 dp[i] 表示組成i的最少硬幣數。dp[0] = 0。初始化給陣列最大值

開始建表，轉移式是這樣dp[i] = min(dp[i], dp[i-coin] + 1)。可以從放這個硬幣(現在的錢-硬幣) + 1而來，或是不放這個硬幣。

建完表後，枚舉 買方 跟 賣方，時間複雜度O(硬幣數 * 最大總和)

比如47元的可能:  

               買方花47元 賣方花0元      ===> 47個硬幣

               買方花48元 賣方花1元      ===> 48個硬幣 

               買方花50元 賣方花3元 ...  ===> 4個硬幣

再來是貪心解，其實貪心就是從大的硬幣開始挑類似前面的題目dp_09，不用建表，也是枚舉2方。

代碼:  

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int x, n;
    int coin[20];
    int dp[205];
    while(cin >> x >> n){
        for(int i = 0; i < n; ++i) cin >> coin[i];
        memset(dp, 0x3f, sizeof dp);
        dp[0] = 0;
        for(int j = 0; j < n; ++j){
            for(int i = coin[j]; i <= 200; ++i){
                dp[i] = min(dp[i-coin[j]]+1, dp[i]);
            }
        }
        int mn = INT_MAX;
        for(int i = 200; i >= x; i--){
            mn = min(mn, dp[i]+dp[i-x]);
        }
        cout << mn << endl;
    }
    return 0;
}
/*
47

2

1 50
*/