knapsack-problem - 用于求解 knapsack-prblm(整数规划)的库

Question

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

提前致谢。

Answer 1

以下是背包问题 (KP) 的一些实现:

• CPLEX 如果您熟悉 CPLEX (IBM)，他们有一个 Knapsack 页面(以及许多其他 IP 公式)here .
• Java:他们也有背包问题的 Java 实现 here . (具体看javaknapsack.mod)
• Python:这是 one example背包问题的多种解决方法。(作者:Dave Eppstein)
• CPP:这是 a Genetic Algorithm implementation KP 的成员。

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