python - 动态规划 : Rod cutting and remembering where cuts are made

Question

所以我在 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]

Answer 1

如果这是问题: 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]