确定是否可以用 N 个面额找零，每个面额只使用一次并且最多使用 k 个硬币

Question

这是换币题的一个版本。因此，这是一个动态规划问题。

我知道如何确定您是否可以找零，如果您最多只能使用每种面额的一枚硬币，或者您是否最多可以使用 k 枚硬币，但不能同时使用这两种硬币。

Answer 1

不就和N个面额一样了，还要加个最后的检查保证N<=k吗？

changeWithN(amt, k){ ... return n<=k ? ñ：-1 }

Answer 2

组合约束非常简单。我们可以构建一个 three-dimensional table ，其维度表示允许的最大硬币数、允许的硬币数量和目标总和，或者我们可以只说 "screw it" 并在简单的递归解决方案之上进行记忆.在 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)

确定是否可以用 N 个面额找零，每个面额只使用一次并且最多使用 k 个硬币

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

algorithm

dynamic-programming

knapsack-problem

coin-change