0-1背包蛮力执行

Question

我在接近一周的任务中挣扎，没有找到解决方案的成功，所以这个网站是我最后的希望。

我有0-1 Knapsack问题，其中有20个项目有着不同的价值观和重量，包装袋的最大重量为524。现在，我需要实现蛮力找到的20项最佳解决方案的子集，这样总权重< = 524和最大值的选择项目。

请您指出或更好地给出详细的实施方案，以分析它是如何工作的！ 非常感谢您

Answer 1

蛮力的想法很简单：

1. 生成的20个项目的所有可能的子集，只保存那些满足你的体重限制。如果你想要看起来很花哨，你甚至可以考虑在不违反重量限制的情况下不能添加任何东西的子集，因为只有这些子集才可能是正确的答案。 O（2^n）
2. 查找具有最大权重的子集。就候选人数量而言是线性的，并且由于我们有O（2^n）个候选人，所以这是O（2^n）。

如果您需要伪代码，请发表评论。

编辑：嘿，这是伪代码以防万一。

GetCandidateSubsets(items[1..N], buffer, maxw) 
    1. addedSomething = false 
    2. for i = 1 to N do 
    3. if not buffer.contains(item[i]) and 
      weight(buffer) + weight(items[i]) <= maxw then 
    4.  add items[i] to buffer 
    5.  GetCandidateSubsets(items[1..N], buffer) 
    6.  remove items[i] from buffer 
    7.  addedSomething = true 
    8. if not addedSomething then 
    9. emit & store buffer 

请注意，GetCandidateSubsets函数效率不高，即使是暴力破解实施。感谢阿米特指出了这一点。作为第一遍优化，您可以对此进行重新设计，以便只对项目集合的组合进行排序，而不是排列组合。

GetMaximalCandidate(candidates[1..M]) 
    1. if M = 0 then return Null 
    2. else then 
    3. maxel = candidates[1] 
    4. for i = 2 to M do 
    5.  if weight(candidates[i]) > weight(maxel) then 
    6.   maxel = candidates[i] 
    7. return maxel