投资组合与回溯的动态规划背包问题

Question

我正在做一个python项目，利用动态规划的背包问题，根据可以投资的金额找到最佳投资。到目前为止，我能够根据名称提出最好的投资，但是我在格式化和获取其余信息以及实现追溯表方面遇到了麻烦。下面是我到目前为止的输出:

import pandas as pd
from itertools import chain
def investmentFilename(file):
df = pd.read_csv(file)
frame = pd.DataFrame(df)
frame = frame.drop(0) # dropping the United States
# print(frame)
return frame
def loadInvestments(frame):
portfolio = []
state = frame['RegionName'].tolist()
avg = frame['Zhvi'].tolist()
dfAvg = pd.DataFrame(avg)
# print(dfAvg)
tenyr = (frame['10Year'].tolist())
tenyr = pd.DataFrame(tenyr)
roi = tenyr.multiply(dfAvg, axis='columns', level=None, fill_value=None)
# print(roi)
# roi = pd.DataFrame(roi)
ROI = roi.values.tolist()
ROI = list(chain.from_iterable(ROI))
print("InvestmentName InvestmentCost EstimatedReturnOnInvestment")
for i in range(len(state)):
portfolio.append([state[i], int(avg[i]), int(ROI[i])])
print(state[i], 't', avg[i], 't', ROI[i])
# print(portfolio)
# portfolio = list(chain.from_iterable(portfolio))
# print(portfolio)
# printing list data
# print("Investment Name:",state)
# print("Investment Cost:", avg)
# print("Estimated Return on Investment:", ROI)
return portfolio
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[2])
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]]
I[i][w] = name[i - 1] + I[i - 1][w - roi[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]
return (I[n][money])
dataFrame = investmentFilename('zhvi-short.csv')
items = loadInvestments(dataFrame)
print(items)
money = 15000 # change the amount of money you want to invest here
# items = [["A", 60, 120], ["B", 100, 20],["C", 120, 30]] # test
# print(items)
val = []
roi = []
for i in items:
val.append(i[1])
roi.append(i[2])
print(optimizeInvestments(items, money))

输出如下:FloridaNew纽约

我想用"one_answers"或者逗号。然后，我希望这些名称的具体投资回报率也输出。

我还需要为最优投资实现一个回溯表。我知道如何在理论上实现回溯表，但我不确定如何实现关于背包问题。

Answer 1

这就是我最终解决这个问题的方法。

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