UVa11259 - Coin Changing Agains(動態規劃、排容原理)

題目大意

這個地方有四個硬幣，你必須用 4 個硬幣組合成 v 元，有 q 個查詢，且每個硬幣數量都會隨之 q 不同，想請問在每次的 q 查詢中所設定的硬幣數量內，最多有幾種組合方法

題目連結

重點觀念

• 了解排容原理
• 了解動態規劃
• 將他們結合應用起來

分析

• 可以發現，普通的動態規劃沒有辦法解決這題，因為他的硬幣數量可能會來到 \(10^6\)
• 此時可以想想有沒有一些方法可以解決呢？
  • 貪心
    似乎有點複雜
  • 排容原理，如果我們先假設這是個無限背包問題，我們要處理一個問題
    • 使用的硬幣數量超過題目上限
      • 這時候我們可以透過一種方始解決，dp[v 元] - dp[v 元 - coin[i] * (d[i]+1)]，我們可以知道一件事，在 coin[i] * d[i] 元 中都可解出來
      • 因此我們可以知道 dp[v 元 - coin[i] * (d[i]+1)]，就是不合法的
      • 此時，可能會有個疑惑，那 dp[v 元 - coin[i] * (d[i]+2)] 我們就不用減嗎？
      • 真的不用，因為 dp[v 元 - coin[i] * (d[i]+1)] 包含 dp[v 元 - coin[i] * (d[i]+2)]
      • 但注意，這邊一定要用 dp[v 元 - coin[i] * (d[i]+1)] 來做，不可用 dp[coin[i] * (d[i]+1)]，因為我們狀態是不斷往後加，如果我們只減掉一開始 dp 的非法的硬幣數量，那後面的非法的硬幣數量與其他組合我們都沒有處理掉
    • 注意，會有重複扣的問題
      • 可能會有一種組合是，coin[i]、coin[j] 都是非法數量，但因為上一點的邏輯而重複扣了兩遍，因此我們必須要給他加回來
      • 可能會有一種組合是，coin[i]、coin[j]、coin[k] 都是非法數量，但因為上一點的邏輯(coin[i]、coin[j])而加回來，因此我們必須要給他扣掉。
      • 因此我們必須是扣掉 -c[1]-c[2]+c[1]*c[2]....-c[1]*c[2]*c[3]*c[4] 的非法數量
      • 最後我們要判斷 v 在減掉這種非法數量時，v 是否還有大於零，因為 v 必須要大於 0 才表示這種非法組合有成立。
      • 再來讓無限背包的dp[v] - 非法數量就是答案

參考連結

UVA 11259 Coin Changing Again by weixin_30416871

心得

一開始我認為這題應該可以用貪心 + dp 的方法解出來XD，後來發現確實有點太難了QQ，太久沒有寫到排容原理的題目，都忘記要這樣想了….

既然複習到了就讓自己未來在用到時可以順利想起來吧!

題目程式碼

會在下面放一些簡單註解，供大家學習時參考。

#include <iostream>
#include <bits/stdc++.h>
#define LOCAL
#define int long long
#define MAXN 100020
using namespace std;
int t;
int c[5];
int d[5];
int q, v;
int dp[MAXN];

int32_t main()
{
#ifdef LOCAL
    freopen("in1.txt", "r", stdin);
#endif // LOCAL
    cin >> t;
    while(t--){
        memset(dp, 0, sizeof(dp));
        for(int i = 0; i < 4; i++) cin >> c[i];
        cin >> q;

        dp[0] = 1;
        for(int i = 0; i < 4; i++){ //無限背包問題
            for(int j = c[i]; j < MAXN; j++){ 
                dp[j] += dp[j - c[i]];
            }
        }

        while(q--){
            for(int i = 0; i < 4; i++) cin >> d[i];
            cin >> v;

            int ans = 0;
            //一共有 16 種組合每一種組合都可能有非法組合，每個硬筆拿或不拿，使用二進位表示
            for(int i = 0; i <= 16-1; i++){ 
                //flag 重複項現在的正負狀態，每有兩個重複項就補回多扣的非法數量
                //x 非法組合的最後的金額(元)是多少
                int x = v, flag = 1; 
                for(int j = 0; j < 4; j++){//這一種組合方式，有沒有使用 coin[j]
                    if(i & (1 << j)){ //如果有
                        flag = -flag; //判斷現在是做補回多扣的非法數量，還是減去非法數量
                        x -= c[j] * (d[j]+1); //x 減掉非法金額(元)
                    }
                }
                //如果 x > 0，標示這種非法數量存在，進行刪減或補回
                if(x >= 0) ans += flag * dp[x]; 
            }
            cout << ans << "\n";
        }
    }
    return 0;
}