时间戳

首页 > 解决方案 > 解可被 3 整除的硬币找零问题（动态规划）

python - 解可被 3 整除的硬币找零问题（动态规划）

问题描述

我最近参加了一次工作面试，面试官要求我调整硬币找零问题，以便只返回能被 3 整除的解决方案。

这个问题不得不使用动态规划的方式来解决硬币找零问题，我有点卡住了。我已经使用生成器解决了它，但是对于更大的数字来说太慢了。

显然要检查一个数字是否可以被三一整除

number%3==0

然后从https://www.geeksforgeeks.org/coin-change-dp-7/给出这个模板

# Dynamic Programming Python implementation of Coin
# Change problem
def count(S, m, n):
 
    # table[i] will be storing the number of solutions for
    # value i. We need n+1 rows as the table is constructed
    # in bottom up manner using the base case (n = 0)
    # Initialize all table values as 0
    table = [0 for k in range(n+1)]
 
    # Base case (If given value is 0)
    table[0] = 1
 
    # Pick all coins one by one and update the table[] values
    # after the index greater than or equal to the value of the
    # picked coin
    for i in range(0,m):
        for j in range(S[i],n+1):
            table[j] += table[j-S[i]]
 
    return table[n]
 
# Driver program to test above function
arr = [50, 20, 10,1] # list of coins
m = len(arr)
n = 10000 # amount
x = count(arr, m, n)
print (x)
 
# This code is contributed by Afzal Ansari

我不明白如何获得解决方案的数量并使用 if 来保持解决方案只能被 3 整除。面试官从未给我答案，我开始怀疑这是否是一项不可能完成的任务。

标签： pythonknapsack-problem

解决方案

推荐阅读