Задача о ранце с topN решений фиксированного размера ⇐ Python

[Anonymous]

У меня вопрос по динамическому программированию. Я пытаюсь найти достаточно хорошее решение на Python для задачи о рюкзаке.

Дополнительные требования:

• Вместо того, чтобы иметь лучшее решение, я ищу лучшие
  topN решения.
• Я ищу решения точного размера S. т. е. количество предметов в рюкзаке должно быть S. Необязательно, если S равно -1 мы принимаем гибкие размеры

Итак, я хочу положить в рюкзак S элементы, чтобы найти наиболее ценную подпоследовательность предметов, вес которой не превышает максимального веса.
Каждый элемент имеет (значение, вес), где значение — это число, а вес — неотрицательное целое число. Максимальный вес – неотрицательное целое число.

Пример:

def knapsack_variant(items, maxweight, S=-1, topN=10):
"""
>>> items = [(4, 12), (2, 1), (6, 4), (1, 1), (2, 2)]
>>> maxweight = 15
>>> S = 4
>>> topN = 3
>>> knapsack_variant(items, maxweight, S, topN)
(11, [(2, 1), (6, 4), (1, 1), (2, 2)])
next two solutions
"""


Подробнее здесь: https://stackoverflow.com/questions/564 ... fixed-size