Gerando o conjunto de potência de uma lista
Tenho que escrever uma implementação de força bruta do problema da mochila. Aqui está o pseudocódigo:
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
Embora o algoritmo seja bastante fácil de implementar, não tenho a menor idéia de como gerar o conjunto de energia de S e alimentar os subconjuntos do conjunto de energia em cada iteração do loop whil
A minha implementação atual usa uma lista de pares para armazenar o peso e o lucro de um item:
list< pair<int, int> > weight_profit_pair;
E eu quero gerar o conjunto de potência desta lista para minha função computeMaxProfit. Existe um algoritmo disponível para gerar subconjuntos de uma lista? Uma lista é o contêiner certo para usar?