Generando el conjunto de potencia de una lista

Tengo que escribir una implementación de fuerza bruta del problema de la mochila. Aquí está el 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

Aunque el algoritmo es bastante fácil de implementar, no tengo la menor idea de cómo generar el conjunto de potencia de S y alimentar los subconjuntos del conjunto de potencia en cada iteración del bucle while.

Mi implementación actual utiliza una lista de pares para mantener el peso y el beneficio de un artículo:

list< pair<int, int> > weight_profit_pair;

Y quiero generar el conjunto de potencia de esta lista para mi función computeMaxProfit. ¿Existe algún algoritmo para generar subconjuntos de una lista? ¿Es una lista el contenedor adecuado para usar?

Respuestas a la pregunta(6)

Su respuesta a la pregunta