我在给定的任务上苦苦挣扎了将近一个星期,但没有成功找到解决方案,所以这个网站是我最后的希望。
我有0-1 背包问题,其中有 20 个具有不同值和重量的物品,麻袋的最大重量是 524。现在我需要实施蛮力来找到 20 个物品的最佳解决方案子集,以便总重量 <= 524 和最大值选择的项目。
您能否指出我或更好地给出详细的实现来分析它是如何工作的!非常感谢
我在给定的任务上苦苦挣扎了将近一个星期,但没有成功找到解决方案,所以这个网站是我最后的希望。
我有0-1 背包问题,其中有 20 个具有不同值和重量的物品,麻袋的最大重量是 524。现在我需要实施蛮力来找到 20 个物品的最佳解决方案子集,以便总重量 <= 524 和最大值选择的项目。
您能否指出我或更好地给出详细的实现来分析它是如何工作的!非常感谢
蛮力的想法很简单:
如果您想要一些伪代码,请发表评论。
编辑:嘿,这是伪代码以防万一。
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