Рюкзак вариант варианта с topN решения фиксированного размера

Question

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

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

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

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

Пример:

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
    """