c - 0-1 Knapsack 的蛮力实现

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