最大收益与能力/成本的优化

Question

给定一组表示(成本、收益)的样本数据

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

我有一个算法，它可以找到这些项目的最佳组合，以填充给定的成本。

F(项目、容量、maxCost)

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

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是最适合的3个(300,100)项目，而3,1100生产最好的1x500和2x300。

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

我尝试过许多变体，包括一个基于产量的变体，但是它们都会变慢(我似乎想不出一个很好的方法来完成在它的一生中没有产生可笑的列表的产量)。

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

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

有没有可能用非蛮力强迫发现？

Answer 1

这看起来很像problem。在一般情况下，这将需要指数时间，但动态规划方法中的一种可能是实用的，特别是如果您准备舍入一些数字来得到对一个四舍五入的问题的精确答案，这将是对您的问题的近似答案。