在背包 0/1 代码中实现回溯 table
Implementing traceback table in knapsack 0/1 code
我正在尝试在我的背包 0/1 问题的动态规划算法中实施回溯 table。在我的代码中,我设置了一个回溯 table 矩阵,但我不确定如何根据我的程序填写这些值。
def optimizeInvestments(invstmt, money):
""" knapsack problem """
n = len(invstmt)
val = []
name = []
roi = []
traceback = [[0 for i in range(n)] for i in range(n)]
for i in invstmt:
name.append(i[0])
val.append(i[-1])
roi.append(i[1])
K = [[0 for x in range(money + 1)] for x in range(n + 1)]
I = [[0 for x in range(money + 1)] for x in range(n + 1)]
for i in range(n + 1):
for w in range(money + 1):
if i == 0 or w == 0:
K[i][w] = 0
I[i][w] = ""
elif roi[i - 1] <= w:
if (val[i - 1] + K[i - 1][w - roi[i - 1]] > K[i - 1][w]):
K[i][w] = val[i - 1] + K[i - 1][w - roi[i - 1]]
if len(I[i - 1][w - roi[i - 1]]) > 0:
I[i][w] = name[i - 1] + " & " + I[i - 1][w - roi[i - 1]]
else:
I[i][w] = name[i - 1]
else:
K[i][w] = K[i - 1][w]
I[i][w] = I[i - 1][w]
else:
K[i][w] = K[i - 1][w]
I[i][w] = I[i - 1][w]
portfolio = 'With $'+ str(money) + ", invest in " + str(I[n][money]) + " for a ROI of $" + str(K[n][money])
return portfolio
想出如何添加回溯 table。这是我的代码:
def optimizeInvestments(invstmt, money):
""" knapsack problem """
n = len(invstmt)
val = []
name = []
roi = []
for i in invstmt:
name.append(i[0])
val.append(i[-1])
roi.append(i[1])
K = [[0 for x in range(money + 1)] for x in range(n + 1)]
I = [[0 for x in range(money + 1)] for x in range(n + 1)]
optimal = [[None for x in range(money + 1)] for x in range(n + 1)]
traceback = [[False for x in range(money + 1)] for x in range(n + 1)]
for i in range(n + 1):
for w in range(money + 1):
optimal[i][w] = 0
if i == 0 or w == 0:
K[i][w] = float(0)
I[i][w] = ""
optimal[i][w] = 0
traceback[i][w] = False
elif roi[i - 1] <= w:
if (val[i - 1] + K[i - 1][w - roi[i - 1]] > K[i - 1][w]):
K[i][w] = val[i - 1] + K[i - 1][w - roi[i - 1]]
optimal[i][w] = val[i - 1] + optimal[i - 1][w - roi[i - 1]]
traceback[i][w] = True
if len(I[i - 1][w - roi[i - 1]]) > 0:
I[i][w] = name[i - 1] + " & " + I[i - 1][w - roi[i - 1]]
else:
I[i][w] = name[i - 1]
else:
K[i][w] = K[i - 1][w]
I[i][w] = I[i - 1][w]
optimal[i][w] = optimal[i-1][w]
traceback[i][w] = False
else:
K[i][w] = K[i - 1][w]
I[i][w] = I[i - 1][w]
optimal[i][w] = optimal[i-1][w]
traceback[i][w] = False
print('optimal: ')
for row in optimal:
print(row)
print("traceback: ")
for row in traceback:
print(row)
我正在尝试在我的背包 0/1 问题的动态规划算法中实施回溯 table。在我的代码中,我设置了一个回溯 table 矩阵,但我不确定如何根据我的程序填写这些值。
def optimizeInvestments(invstmt, money):
""" knapsack problem """
n = len(invstmt)
val = []
name = []
roi = []
traceback = [[0 for i in range(n)] for i in range(n)]
for i in invstmt:
name.append(i[0])
val.append(i[-1])
roi.append(i[1])
K = [[0 for x in range(money + 1)] for x in range(n + 1)]
I = [[0 for x in range(money + 1)] for x in range(n + 1)]
for i in range(n + 1):
for w in range(money + 1):
if i == 0 or w == 0:
K[i][w] = 0
I[i][w] = ""
elif roi[i - 1] <= w:
if (val[i - 1] + K[i - 1][w - roi[i - 1]] > K[i - 1][w]):
K[i][w] = val[i - 1] + K[i - 1][w - roi[i - 1]]
if len(I[i - 1][w - roi[i - 1]]) > 0:
I[i][w] = name[i - 1] + " & " + I[i - 1][w - roi[i - 1]]
else:
I[i][w] = name[i - 1]
else:
K[i][w] = K[i - 1][w]
I[i][w] = I[i - 1][w]
else:
K[i][w] = K[i - 1][w]
I[i][w] = I[i - 1][w]
portfolio = 'With $'+ str(money) + ", invest in " + str(I[n][money]) + " for a ROI of $" + str(K[n][money])
return portfolio
想出如何添加回溯 table。这是我的代码:
def optimizeInvestments(invstmt, money):
""" knapsack problem """
n = len(invstmt)
val = []
name = []
roi = []
for i in invstmt:
name.append(i[0])
val.append(i[-1])
roi.append(i[1])
K = [[0 for x in range(money + 1)] for x in range(n + 1)]
I = [[0 for x in range(money + 1)] for x in range(n + 1)]
optimal = [[None for x in range(money + 1)] for x in range(n + 1)]
traceback = [[False for x in range(money + 1)] for x in range(n + 1)]
for i in range(n + 1):
for w in range(money + 1):
optimal[i][w] = 0
if i == 0 or w == 0:
K[i][w] = float(0)
I[i][w] = ""
optimal[i][w] = 0
traceback[i][w] = False
elif roi[i - 1] <= w:
if (val[i - 1] + K[i - 1][w - roi[i - 1]] > K[i - 1][w]):
K[i][w] = val[i - 1] + K[i - 1][w - roi[i - 1]]
optimal[i][w] = val[i - 1] + optimal[i - 1][w - roi[i - 1]]
traceback[i][w] = True
if len(I[i - 1][w - roi[i - 1]]) > 0:
I[i][w] = name[i - 1] + " & " + I[i - 1][w - roi[i - 1]]
else:
I[i][w] = name[i - 1]
else:
K[i][w] = K[i - 1][w]
I[i][w] = I[i - 1][w]
optimal[i][w] = optimal[i-1][w]
traceback[i][w] = False
else:
K[i][w] = K[i - 1][w]
I[i][w] = I[i - 1][w]
optimal[i][w] = optimal[i-1][w]
traceback[i][w] = False
print('optimal: ')
for row in optimal:
print(row)
print("traceback: ")
for row in traceback:
print(row)