knapsack-problem - 解决背包-prblm（整数编程）的库

Question

我正在尝试解决背包问题，这也是一个整数规划问题。我研究了几种近似解决方案，例如动态规划、贪心算法、分支定界算法、遗传算法。你能告诉我一个有助于实现任何/所有这些算法的库（用任何语言）吗？

提前致谢。

Answer 1

以下是背包问题（KP）的一些实现：

• CPLEX如果您熟悉 CPLEX (IBM)，他们在此处有一个关于背包（在许多其他 IP 公式中）的页面。
• Java：他们在这里也有背包问题的 Java 实现。（具体看javaknapsack.mod）
• Python：这是背包问题的多种解决方案技术的一个示例。（戴夫·埃普斯坦（Dave Eppstein））
• CPP：这是 KP的遗传算法实现。

一个简单的网络搜索应该会为您提供更多示例，因为使用您提到的几种技术很容易解决（和教授）背包问题。