投資組合動態規劃的背包問題和回溯

我正在開發一個 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 York

我想用“和”或逗號分隔。然后我希望輸出每個名稱的特定投資回報率。

我還需要為最佳投資實施追溯表。我在理論上知道如何實作回溯表，但對于背包問題我不確定如何實作。

uj5u.com熱心網友回復：

這就是我最終想出的解決這個問題的方法。

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

標籤：Python 熊猫 算法 动态规划 背包问题

上一篇：根據經度和緯度計算離我最近的商店

下一篇：將整數N并行劃分為M個部分