Red Huang

找零问题的各种延伸问题

能否凑得某个价位（找零问题）

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. }

凑得某个价位的凑法共有几种（硬币找零问题）

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. }

凑得某个价位的最少钱币用量（找零问题）

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. }