我尝试了使用分支和定界实现here背包问题
该解决方案看起来不错,但它没有给出最终选定的项目以达到最佳值。 有没有一种方法可以通过最低限度地更改以下代码来实现这一点
import sys
def bound(vw, v, w, idx):
if idx >= len(vw) or w > limit:
return -1
else:
while idx < len(vw) and w + vw[idx][1] <= limit:
v, w, idx = v + vw[idx][0], w + vw[idx][1], idx + 1
if idx < len(vw):
v += (limit - w) * vw[idx][0] / (vw[idx][1] * 1.0)
return v
def knapsack(vw, limit, curValue, curWeight, curIndex):
global maxValue
if bound(vw, curValue, curWeight, curIndex) >= maxValue:
if curWeight + vw[curIndex][1] <= limit:
maxValue = max(maxValue, curValue + vw[curIndex][0])
knapsack(vw, limit, curValue + vw[curIndex][0], curWeight + vw[curIndex][1], curIndex + 1)
if curIndex < len(vw) - 1:
knapsack(vw, limit, curValue, curWeight, curIndex + 1)
return maxValue
maxValue = 0
if __name__ == '__main__':
with open(sys.argv[1] if len(sys.argv) > 1 else sys.exit(1)) as f:
n, limit = map(int, f.readline().split())
vw = []
taken = n * [0]
for ln in f.readlines():
vl, wl = map(int, ln.split())
vw.append([vl, wl, vl / (wl * 1.0)])
print(knapsack(sorted(vw, key=lambda x: x[2], reverse=True), limit, 0, 0, 0))
print(taken)
假设我们有一个包含以下内容的输入文件
4 11
8 4
15 8
4 3
10 5
我期待的结果如下
19
0 1 1 0
我编写了自己的implementation,它给出了上述所需的输出,但是对于像这样的大问题one来说,它花费的时间太长了
我重新组织了提供的代码,然后添加了逻辑以跟踪最佳选择。由于您希望该选择是一个由0和1组成的列表,因此我使用了一个位图(一个大整数),每个项目都在该位图中分配了一个位
下面是它的外观:
相关问题 更多 >
编程相关推荐