algorithm - Determine if you can make change with N denominations using each denomination only once and with at most k coins

Question

This is a version of the coin-changing problem. As such, it is a dynamic programming problem.

I know how to determine if you can make change if either you can use at most one coin of each denomination or if you can use at most k coins, but not both.

Answer 1

结合约束是相当简单的。我们可以构建一个三维表，其维度表示允许的最大硬币、允许的硬币数量和目标总和，或者我们可以说“搞砸了”，然后在简单的递归解决方案之上进行记忆。在 Python 中：

# Assume we have a memoization decorator.
# functools.lru_cache(maxsize=None) would do.
@memoize
def knapsack_possible(coin_tuple, target, k):
    if not target:
        # Target achieved.
        return True
    elif not coin_tuple or not k:
        # Out of coins.
        return False
    else:
        return (knapsack_possible(coin_tuple[:-1], target, k) or
                knapsack_possible(coin_tuple[:-1], target-coin_list[-1], k-1)

Answer 2

会不会和 N 面额一样，但是添加另一个最终检查以确保 N<=k？

changeWithN(amt, k){ ... 返回 n<=k ？n : -1 }