问题遇到的现象和发生背景
我想要写一些代码，用栈模拟递归解决找零钱问题
然后我想了很久的代码，可总是会有问题，数字小没有问题，可一旦数字大起来，不但不好Debug，而且答案也不对
我下面的代码该怎么修改才能正确，或者写怎样的代码能解决这道问题(Python或者伪代码， 所写代码为Python)
原题目是一个客户来到商店，买了37元的东西，他给了服务员100元，服务员现在手头有1元, 3元， 5元,10元，21元和25元的纸币，请问服务员最少要给客户几张纸币(元不能重复输入，并不是我不想每个后面都加上元)
问题相关代码，请勿粘贴截图
from DoStack import Stack
def recDC(coinValueList, change, knownResults):
"""
:param coinValueList: list -> hava denominations of money
:param change: int -> amount of money to change
:param knownResults: list -> number of steps per known solution
:return: int -> optimal solution
"""
stack = Stack()
stack.push([[coinValueList, change, knownResults], []])
# stack[0] is list of parameter stack[0][0] is coins stack[0][1] is amount stack[0][2] is list of money
# stack[1] is list of return value
"""
minCoins = change
if change in coinValueList: # 递归结束基本条件
knownResults[change] = 1 # 记录最优解
return 1
elif knownResults[change] > 0:
return knownResults[change] # 查表成功,直接使用最优解
else:
for i in [c for c in coinValueList if c <= change]:
numCoins = 1 + recDC(coinValueList, change - i, knownResults)
if numCoins < minCoins:
minCoins = numCoins
# 找到最优解,记录到表中
knownResults[change] = minCoins
return minCoins
"""
while not stack.isEmpty():
f = stack.pop()
flag = False
minCoins = f[0][1]
if f[0][1] in f[0][0]:
f[0][2][f[0][1]] = 1
if stack.isEmpty():
return 1
minCoins = 1
elif f[0][2][f[0][1]] > 0:
if stack.isEmpty():
return f[0][2][f[0][1]]
minCoins = f[0][2][f[0][1]]
else:
l = []
for c in f[0][0]:
if c <= f[0][1]:
l.append(c)
for i in l:
if len(f[1]) < l.index(i) + 1:
stack.push(f)
stack.push([[f[0][0], f[0][1] - i, f[0][2]], []])
flag = True
break
else:
if f[1][l.index(i)] + 1 < minCoins:
minCoins = f[1][l.index(i)] + 1
f[0][2][f[0][1]] = minCoins
if flag:
continue
elif flag:
continue
else:
f = stack.pop()
stack.push([[f[0][0], f[0][1], f[0][2]], [minCoins]])
print(recDC([1, 3, 5, 10, 21, 25], 63, [0] * (63 + 1)))
Stack代码
class Stack(object):
def __init__(self):
self.Stack = list()
def push(self, item):
self.Stack.append(item)
def peek(self):
return self.Stack[-1]
def pop(self):
_return = self.Stack[-1]
self.Stack.pop()
return _return
def isEmpty(self):
if len(self.Stack) != 0:
return False
return True
def size(self):
return len(self.Stack)
def number(self):
return self.Stack
运行结果及报错内容
理想的结果应该是3， 可运行出的答案却是39，
我的解答思路和尝试过的方法
我开始是想将问题分解成一个个子问题压入栈，可是代码实现起来却难如登天，最后我选择用二叉树的画法的思路(先将一条进行到底，然后一步步往回退)，但还是没有达到效果，Debug了半天也没找到问题所在，括号多出天际， 看起来贼费劲，最后搞不下去了，还有没有其他的办法可以解决这个问题啊
我想要达到的结果
运行出来答案是3，而不是39
