Я должен написать грубую реализацию проблемы с рюкзаком. Вот псевдокод:

computeMaxProfit(weight_capacity)
    max_profit = 0
    S = {} // Each element of S is a weight-profit pair.
    while true
        if the sum of the weights in S <= weight_capacity
            if the sum of the profits in S > max_profit
                update max_profit
        if S contains all items // Then there is no next subset to generate
            return max
        generate the next subset S

Хотя алгоритм довольно прост в реализации, я не имею ни малейшего представления о том, как генерировать набор мощности S и подавать поднаборы набора мощности в каждую итерацию цикла while.

Моя текущая реализация использует список пар для хранения веса и прибыли элемента:

list< pair<int, int> > weight_profit_pair;

И я хочу сгенерировать набор мощности этого списка для моей функции computeMaxProfit. Есть ли алгоритм для создания подмножеств списка? Является ли список правильным контейнером для использования?