1

我在给定的任务上苦苦挣扎了将近一个星期，但没有成功找到解决方案，所以这个网站是我最后的希望。

我有0-1 背包问题，其中有 20 个具有不同值和重量的物品，麻袋的最大重量是 524。现在我需要实施蛮力来找到 20 个物品的最佳解决方案子集，以便总重量 <= 524 和最大值选择的项目。

您能否指出我或更好地给出详细的实现来分析它是如何工作的！非常感谢

4

1 回答 1

6

蛮力的想法很简单：

  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
于 2011-10-31T14:08:34.160 回答