python - 优化最佳增益与容量/成本

Question

给定一组代表(成本， yield )的样本数据

items = [ (1000, 300), (500, 150), (400, 120), (300, 100), (200, 50), (55, 25) ]

我有一个算法可以找到这些项目的倍数的最佳组合来填补给定的成本

f(项目，容量，最大成本)

将生成一个条目，指定受容量和成本限制的最有效的项目数量。

class BestCombo(object):

    def __init__(self, items, qtyLimit, costLimit):
      self.bestPerf  = 0
      self.best      = None
      self.items     = items
      self.qtyLimit  = qtyLimit
      self.costLimit = costLimit

      self._findBest(load=[], qty=0, cost=0, perf=0)

    def _findBest(self, load, qty, cost, perf):
      idx = len(load)
      if idx >= len(self.items):
        if qty <= self.qtyLimit and cost <= self.costLimit:
          if perf > self.bestPerf:
            self.bestPerf = perf
            self.best = list(load)
        return

      item = self.items[idx]
      maximum = min(self.qtyLimit - qty, (self.costLimit - cost) // item[0])
      for q in range(0, maximum + 1):
        self._findBest(load + [[item, q]], qty + q, cost + item[0] * q, perf + item[1] * q)

items = [ (1000, 300), (500, 150), (400, 120), (300, 100), (200, 50), (55, 25) ]
print("3, 900")
print(BestCombo(items, 3, 900).best)
print("3, 1100")
print(BestCombo(items, 3, 1100).best)
print("3, 3000")
print(BestCombo(items, 3, 3000).best)
print("10, 900")
print(BestCombo(items, 10, 900).best)
print("42, 21000")
print(BestCombo(items, 42, 21805).best)

所以这会产生一个“最佳”，表示 3 个单位的 900 perf 最适合 (300,100) 项中的 3 个，而 3, 1100 会产生 1x500 和 2x300 的最佳值。

虽然这种方法有效，但对于非平凡的值来说速度非常慢。

我尝试了多种变体，包括基于产量的变体，但它们都因某些变体而变慢(我似乎无法想出一个好的方法来实现不会产生荒谬的产量生命周期中的列表数)

“项目”列表可能最多有 64-90 个项目，容量不太可能超过 255 个。

我似乎记得过去使用算法来解决这个问题，但是，也许是因为我对 Python 比较陌生，而且我是用 Python 做的，所以我在那里画了一个空白。

是否可以通过非暴力破解找到结果？

Answer 1

这看起来很像 http://en.wikipedia.org/wiki/Knapsack_problem .在一般情况下，这将花费指数时间，但其中一种动态规划方法可能会被证明是实用的，特别是如果您准备对一些数字进行四舍五入以获得对四舍五入数字问题的准确答案，这将是一个您的问题的大致答案。