计算从有限数量的硬币中形成最小数量硬币（或任何有效数量的硬币）的硬币的简单算法

Question

我需要找到组成指定数量所需的硬币，而不是方式的数量或硬币的最小数量，但如果硬币最终达到最小数量，那是理想的。

比如我们有硬币(1,5,25,50)，我们要补200的数量

如果我们有无限数量的硬币，我们将得到 (50, 50, 50, 50) 作为最小硬币数量。但是如果我们对代币有限制，例如最多两个 50，五个 25，那么我们将无法得到该结果，而是另一个硬币列表：50、50、25、25、25、25（更多硬币，但这并不重要）。

如果无法组合硬币，则返回一个空集合。

我看到了一些不清楚的解释，所以我想弄清楚：想一想如果您要编写此代码以供其他开发人员维护，那么您将如何编写代码？

编码示例将是理想的（首选 C 语法语言），但伪代码也应该可以工作，如果它像它应该的那样清晰或更清晰的话；如果你想两者都做我的客人。

我认为算法的复杂度不应超过 O(n*k)。

这可能是迄今为止我所看到的最接近的东西，但接受的答案对我来说并不清楚（任何可以解释它的人，特别是 k 部分得到奖励积分）：

如果你能想出一个测试，加分。

感谢您的帮助！

Answer 1

感谢@user3386109 和@RBarryYoung；我的答案基于子集和问题和动态规划解决方案：

public List<Integer> makeChange(int[] coins, int amount) {
    var coinsSumToAmount = new boolean[coins.length][amount + 1];

    for (int row = 0; row < coins.length; row++) {
        coinsSumToAmount[row][0] = true;
        for (int col = 1; col <= amount; col++) {
            if (row == 0) {
                if (col == coins[row]) {
                    coinsSumToAmount[row][col] = true;
                }
            }
            else {
                if (col < coins[row]) {
                    coinsSumToAmount[row][col] = coinsSumToAmount[row - 1][col];
                }
                else { // col >= coin
                    coinsSumToAmount[row][col] = coinsSumToAmount[row - 1][col] || coinsSumToAmount[row - 1][col - coins[row]];
                }
            }
        }
    }

    if (coinsSumToAmount[coins.length - 1][amount]) {
        // Backtrack to find actual coins
        List<Integer> change = new ArrayList<>();
        for (int row = coins.length - 1, col = amount; row >= 0 && col != 0; row--) {
            if (row == 0 && coinsSumToAmount[row][col]) {
                change.add(coins[row]);
            }
            else if (coinsSumToAmount[row][col] != coinsSumToAmount[row - 1][col]) {
                change.add(coins[row]);
                col -= coins[row];
            }
        }
        return change;
    }
    else { // No solution found
        return List.of();
    }
}

计算从有限数量的硬币中形成最小数量硬币（或任何有效数量的硬币）的硬币的简单算法

Simple algorithm to compute coins that form minimum number of coins (or any valid number of coins) from a limited number of coins

algorithm

dynamic-programming

coin-change