当前位置：文江博客话题详情

0-1 Knapsack 的暴力破解实现

发布于 2024-12-12 13:30:14 字数 304 浏览 0 评论 0原文

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

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

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

原文

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

太傻旳人生 2024-12-19 13:30:14

蛮力的想法很简单：

生成 20 件物品的所有可能子集，仅保存那些满足重量限制的物品。如果您想变得更奇特，您甚至可以只考虑在不违反权重约束的情况下无法添加任何其他内容的子集，因为只有这些子集可能是正确的答案。 O(2^n)
找到权重最大的子集。就候选数量而言是线性的，并且由于我们有 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

The brute-force idea is easy:

Generate all possible subsets of your 20 items, saving only those which satisfy your weight constraint. If you want to be fancy, you can even only consider subsets to which you cannot add anything else without violating the weight constraint, since only these can possibly be the right answer. O(2^n)
Find the subset with maximum weight. linear in terms of the number of candidates, and since we have O(2^n) candidates, this is O(2^n).

Please comment if you'd like some pseudocode.

EDIT: What the hey, here's the pseudocode just in case.

  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

Note that the GetCandidateSubsets function is not very efficient, even for a brute force implementation. Thanks to amit for pointing that out. You could rework this to only walk the combinations, rather than the permutations, of the item set, as a first-pass optimization.

  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

回复收藏 0 原文

~没有更多了~