gpt4 book ai didi

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

转载 作者:塔克拉玛干 更新时间:2023-11-03 04:22:29 27 4
gpt4 key购买 nike

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

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

最佳答案

组合约束非常简单。我们可以构建一个三维表,其维度表示允许的最大硬币数、允许的硬币数和目标总和,或者我们可以说“去他的”并在简单的递归解决方案之上进行内存。在 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)

关于algorithm - 确定是否可以用 N 个面额找零,每个面额只使用一次并且最多使用 k 个硬币,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/34886963/

27 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com