Red Huang

Money Changing Problem 的各種延伸問題

能否湊得某個價位（ Money Changing Problem ）

2. int price [5] = {5, 2, 6, 11, 17};   // 各種面額，順序可隨意。

3. bool c[1000+1];

4. // 看看 {5, 2, 6, 11, 17} 這些面額湊不湊得到價位 m

5. void change(int m)

6. {

7.     memset(c, false, sizeof(c));

8.     c[0] = true;

9.     for (int i = 0; i < 5; ++i)             // 依序加入各種面額

10.         for (int j = price [i]; j <= m; ++j) // 由低價位逐步到高價位

11.             c [j] ||= c [j-price [i]];         // 湊、湊、湊

12.     if (c[m])

13.         cout << "湊得到";

14.     else

15.         cout << "湊不到";

16. }

17. int price[5] = {5, 2, 6, 11, 17};

18. int c [5][1000+1];   // 大於等於 0 代表該問題有計算過，-1 代表沒計算過。

19.                     // 一開始必須全部初始化為 - 1。

20. void change(int n, int m)

21. {

22.     if (n < 0 || m < 0) return 0;   // 0 代表 false

23.     if (m == 0) return 1;           // 1 代表 true

24.     if (c[n][m] != -1) return c[n][m];

25.     return c[n][m] = change(n-1, m) | change(n, m - price[n]);

26. }

湊得某個價位的湊法共有幾種（ Coin Change Problem ）

2. int price[5] = {5, 2, 6, 11, 17};

3. int c[1000+1];

4. void change(int m)

5. {

6.     memset(c, 0, sizeof(c));

7.     c[0] = 1;

8.     for (int i = 0; i < 5; ++i)

9.         for (int j = price[i]; j <= m; ++j)

10.             c[j] += c[j-price[i]];

11.     cout << "湊得價位" << m << "的湊法有" << c [m] << "種";

12. }

湊得某個價位的最少錢幣用量（ Change-Making Problem ）

2. int price[5] = {5, 2, 6, 11, 17};

3. int c[1000+1];

4. void change(int m)

5. {

6.     memset(c, 0x7f, sizeof(c));

7.     c[0] = 0;

8.     for (int i = 0; i < 5; ++i)

9.         for (int j = price[i]; j <= m; ++j)

10.             c[j] = min(c[j], c[j-price[i]] + 1);

11.     cout << "湊得價位" << m;

12.     cout << "最少需（只）要" << c [m] << "個錢幣";

13. }

湊得某個價位的錢幣用量，有哪幾種可能性。

2. int price[5] = {5, 2, 6, 11, 17};

3. long long c [1000];  // 每一格都是一個 bitset，

4.                     // 紀錄該價位可用幾個錢幣湊得，包含各種可能性。

5. void change(int m)

6. {

7.     memset(c, 0, sizeof(c));

8.     c[0] = 1;

9.     for (int i = 0; i < 5; ++i)

10.         for (int j = price[i]; j <= m; ++j)

11.             // 錢幣數量加一，每一種可能性都加一。

12.             c[j] |= c[j-price[i]] << 1;

13.     for (int i = 1; i <= 63; ++i)

14.         if (c[m] & (1 << i))

15.             cout << "用" << i << "個錢幣可湊得價位" << m;

16. }

能否湊得某個價位，但是錢幣限量供應。

2. int price[5] = {5, 2, 6, 11, 17};

3. int num [5] = {4, 5, 5, 3, 2};   // 各種面額的供應量

4. bool c[1000+1];

5. void change(int m)

6. {

7.     memset(c, 0, sizeof(c));

8.     c[0] = true;

9.     for (int i = 0; i < 5; ++i)

10.         for (int k = 0; k < M [i]; ++k)  // 各種餘數分開處理

11. //      for (int k = 1; k <= M [i]; ++k) // 快了那麼一點的寫法

12.         {

13.             int left = T[i];

14.             for (int j = k; j <= m; j += M [i])  // 由低價位到高價位

15.                 // 用第 0 種到第 i 種面額已能湊得，錢幣可以省著用。

16.                 if (c[j])

17.                 {

18.                     left = T [i];    // 補充彈藥

19.                 }

20.                 // 過去都無法湊得，一定要試著用目前面額硬湊。

21.                 else if (left > 0)

22.                 {

23.                     left--; // 用掉一個錢幣

24.                     c[j] = true;

25.                 }

26.         }

27.     if (c[m])

28.         cout << "湊得到";

29.     else

30.         cout << "湊不到";

31. }