用python几乎解决了0/1二维背包问题

2024-03-28 16:25:05 发布

您现在位置:Python中文网/ 问答频道 /正文

我试图从这个列表中选择最多10个项目,以获得更高的利润。在

  Item name | Item "Weight" | Item "Profit"

         [A, 1084, 424],
         [B, 1143, 391],
         [C, 1205, 351],
         [D, 1088, 328],
         [E, 5, 21],
         [F, 996, 241],
         [G, 13, 23],
         [H, 2, 9],
         [I, 5, 13],
         [J, 14, 21],
         [K, 11, 18],
         [L, 4, 12],
         [M, 121, 59],
         ...
    Total length: 249

我发现我的问题可以定义为0/1 Bidimensional Knapsack problem。重量将是第一个维度,10个项目的限制将是第二个维度。所以我用python尝试了不同的解决方案来优化选择。在

在搜索了不同的源代码后,我无法找到解决我的特定问题的python解决方案:

  • 规定重量限制(介于100-10000之间)
  • 每个项目只能选择一次
  • 总共只能选择10个项目
  • 最大化“利润”!在

最后,我找到了我试图翻译的thisjava解决方案,但是a在某个地方犯了一个错误,该函数几乎可以正常工作,但却找不到正确的解决方案。我花了几天时间试图找出代码失败的地方,但这有点令人困惑。在

^{pr2}$

这就是输出,有时它会显示出更好的结果,但永远不会是正确的解决方案:

Final size 0 / 800
Final volume 0 / 10
Final value 0

上下文:Windows 8.1 32位。Ipython笔记本。Python 2。在

有什么建议可以让代码生效吗?提前谢谢你!在


Tags: 项目代码name列表定义地方解决方案item
1条回答
网友
1楼 · 发布于 2024-03-28 16:25:05
最后,在ypthon中使用Cython更容易,“翻译”C++算法found here。在

以下是所需的导入:

%load_ext Cython

一定要先安装cython extension。在

以下是上一个链接中的“Cython”版本代码:

^{pr2}$

py背包函数是一个python“包装器”,因此可以在python中使用C函数。在

相关问题 更多 >