我必须写一个背包问题的蛮力实现。这是伪代码:
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 函数生成这个列表的幂集。是否有一种算法可以生成列表的子集?列表是正确的容器吗?