Блог

Приведен примерный набор данных, представляющих (стоимость, коэффициент усиления)

 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 лучше всего подходят для 3 из (300,100) элементов, в то время как 3,1100 дают наилучшие значения 1×500 и 2×300.

Хотя этот подход работает, он очень медленный для нетривиальных значений.

Я перепробовал несколько вариантов, включая вариант, основанный на доходности, но все они из-за некоторых вариаций замедляются (похоже, я не смог придумать хорошего способа получения доходности, который не генерировал бы смехотворное количество списков за все время своего существования)

Список «элементы» потенциально может содержать максимум 64-90 элементов, емкость вряд ли будет намного выше 255.

Кажется, я помню, как в прошлом использовал алгоритм для решения этой проблемы, но, возможно, потому, что я относительно новичок в Python и делаю это на Python, я рисую там пробел.

Возможно ли выполнить поиск без применения грубой силы?

Это очень похоже http://en.wikipedia.org/wiki/Knapsack_problem. В общем случае это займет экспоненциальное время, но один из подходов динамического программирования может оказаться практичным, особенно если вы готовы округлить некоторые числа, чтобы получить точный ответ на задачу с округленными числами, который будет приблизительным ответом на вашу проблему.