元素最佳组合的收敛性

Question

你有1万美元可以投资于股票。你会收到一份200只股票的清单，并被告知选择8只股票去购买，并指出你想购买的股票有多少。单在一只股票上的花费不能超过2,500美元，每只股票的价格从100美元到1000美元不等。你不能买一小部分股票，只买整数。每只股票也有一个附加价值，表明它有多有利可图。这是一个从0到100的任意数字，作为一个简单的评级系统.

最终目标是列出8只股票的最佳选择，并指出每只股票的最佳购买量，而不超过每只股票的2,500美元上限。

·我不是在征求投资建议，而是选择股票，因为它可以很好地比喻我试图解决的实际问题。

·我所看到的似乎是0/1背包问题的一个更复杂的版本：problem。

-不，这不是作业。

Answer 1

下面是一些经过简单测试的代码，用于及时解决您的问题--即可用资金数量的多项式，您拥有的股票数量，以及您可以购买的最大股票数量。

#! /usr/bin/env python
from collections import namedtuple

Stock = namedtuple('Stock', ['id', 'price', 'profit'])

def optimize (stocks, money=10000, max_stocks=8, max_per_stock=2500):
    Investment = namedtuple('investment', ['profit', 'stock', 'quantity', 'previous_investment'])
    investment_transitions = []
    last_investments = {money: Investment(0, None, None, None)}
    for _ in range(max_stocks):
        next_investments = {}
        investment_transitions.append([last_investments, next_investments])
        last_investments = next_investments


    def prioritize(stock):
        # This puts the best profit/price, as a ratio, first.
        val = [-(stock.profit + 0.0)/stock.price, stock.price, stock.id]
        return val

    for stock in sorted(stocks, key=prioritize):
        # We reverse transitions so we have not yet added the stock to the
        # old investments when we add it to the new investments.
        for transition in reversed(investment_transitions):
            old_t = transition[0]
            new_t = transition[1]
            for avail, invest in old_t.iteritems():
                for i in range(int(min(avail, max_per_stock)/stock.price)):
                    quantity = i+1
                    new_avail = avail - quantity*stock.price
                    new_profit = invest.profit + quantity*stock.profit
                    if new_avail not in new_t or new_t[new_avail].profit < new_profit:
                        new_t[new_avail] = Investment(new_profit, stock, quantity, invest)
    best_investment = investment_transitions[0][0][money]
    for transition in investment_transitions:
        for invest in transition[1].values():
            if best_investment.profit < invest.profit:
                best_investment = invest

    purchase = {}
    while best_investment.stock is not None:
        purchase[best_investment.stock] = best_investment.quantity
        best_investment = best_investment.previous_investment

    return purchase


optimize([Stock('A', 100, 10), Stock('B', 1040, 160)])

在这一点上，一旦我们看到继续增加股票是不可能改善的，那就是删除投资的微小优化。这可能比用您的数据运行的旧代码快几个数量级。

#! /usr/bin/env python
from collections import namedtuple

Stock = namedtuple('Stock', ['id', 'price', 'profit'])

def optimize (stocks, money=10000, max_stocks=8, max_per_stock=2500):
    Investment = namedtuple('investment', ['profit', 'stock', 'quantity', 'previous_investment'])
    investment_transitions = []
    last_investments = {money: Investment(0, None, None, None)}
    for _ in range(max_stocks):
        next_investments = {}
        investment_transitions.append([last_investments, next_investments])
        last_investments = next_investments


    def prioritize(stock):
        # This puts the best profit/price, as a ratio, first.
        val = [-(stock.profit + 0.0)/stock.price, stock.price, stock.id]
        return val

    best_investment = investment_transitions[0][0][money]
    for stock in sorted(stocks, key=prioritize):
        profit_ratio = (stock.profit + 0.0) / stock.price
        # We reverse transitions so we have not yet added the stock to the
        # old investments when we add it to the new investments.
        for transition in reversed(investment_transitions):
            old_t = transition[0]
            new_t = transition[1]
            for avail, invest in old_t.items():
                if avail * profit_ratio + invest.profit <= best_investment.profit:
                    # We cannot possibly improve with this or any other stock.
                    del old_t[avail]
                    continue
                for i in range(int(min(avail, max_per_stock)/stock.price)):
                    quantity = i+1
                    new_avail = avail - quantity*stock.price
                    new_profit = invest.profit + quantity*stock.profit
                    if new_avail not in new_t or new_t[new_avail].profit < new_profit:
                        new_invest = Investment(new_profit, stock, quantity, invest)
                        new_t[new_avail] = new_invest
                        if best_investment.profit < new_invest.profit:
                            best_investment = new_invest

    purchase = {}
    while best_investment.stock is not None:
        purchase[best_investment.stock] = best_investment.quantity
        best_investment = best_investment.previous_investment

    return purchase