所以我在 python 中有这段代码,目前它只返回切割杆的最大值。我怎样才能修改它以让我也知道切割的位置?它采用一个价格列表,其指数 +1 对应于每个长度的杆的值(value),n 对应于杆的长度。
问题:http://www.radford.edu/~nokie/classes/360/dp-rod-cutting.html
def cutRod(price, n):
val = [0 for x in range(n+1)]
val[0] = 0
for i in range(1, n+1):
max_val = 0
for j in range(i):
max_val = max(max_val, price[j] + val[i-j-1])
val[i] = max_val
return val[n]
最佳答案
如果这是问题: Rod cutting
假设代码工作正常,您将必须添加一个条件而不是 Max 操作来检查两个中的哪一个被选中并将那个放入数组中:
def cutRod(price, n):
val = [0 for x in range(n+1)]
val[0] = 0
output = list()
for i in range(1, n+1):
max_val = 0
cur_max_index = -1
for j in range(i):
cur_val = price[j] + val[i-j-1]
if(cur_val>max_val):
max_val = cur_val #store current max
cur_max_index = j #and index
if cur_max_index != -1:
output.append(cur_max_index) #append in output index list
val[i] = max_val
print(output) #print array
return val[n]
关于python - 动态规划 : Rod cutting and remembering where cuts are made,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/47085156/