Money Changing Problem

Money Changing Problem 的各種延伸問題

 

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

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


2. bool c[1000+1];


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


4. void change(int m)


5. {


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


7.     c[0] = true;


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.     if (c[m])


12.         cout << "湊得到";


13.     else


14.         cout << "湊不到";


15. }

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


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


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


4. void change(int n, int m)


5. {


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


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


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


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


10. }

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

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


2. int c[1000+1];


3. void change(int m)


4. {


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


6.     c[0] = 1;


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


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


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


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


11. }

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

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


2. int c[1000+1];


3. void change(int m)


4. {


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


6.     c[0] = 0;


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


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


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


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


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


12. }

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

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


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


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


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.             // 錢幣數量加一，每一種可能性都加一。


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


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


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


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


15. }

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

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


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


3. bool c[1000+1];


4. void change(int m)


5. {


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


7.     c[0] = true;


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


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


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


11.         {


12.             int left = T[i];


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


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


15.                 if (c[j])


16.                 {


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


18.                 }


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


20.                 else if (left > 0)


21.                 {


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


23.                     c[j] = true;


24.                 }


25.         }


26.     if (c[m])


27.         cout << "湊得到";


28.     else


29.         cout << "湊不到";


30. }