0

我的二进制编程问题是：

max: (a1 * x1) + (a2 * x2) + ..... + (an * xn)

受制于：

(c1 * x1) + (c2 * x2) + ..... + (cn * xn) < C

n = 10

a1, ... an, c1, ... cn, C are known

x1, ... xn are binary

这是一个流程任务分配问题。就我而言，解决二进制/整数编程问题的开销需要非常小（< 1 毫秒）。当我使用 CBC 求解器/lpsolve 运行它时，它报告的时间为 2 毫秒 - 7 毫秒。我没有 SCIP/Gurobi。有没有办法在不到一毫秒的时间内解决这个问题？期望在不到一毫秒的时间内解决这个问题似乎是合理的吗？

（我确实禁用了 CBC 中的 printf。但我不确定它是否有任何其他系统操作被卡住......它正在写入的任何日志文件）

4

1 回答 1

0

这是标准的背包问题，可以使用动态规划有效地解决。这已在背包 wiki中进行了很好的讨论（以及多个堆栈溢出帖子，例如这里DP algo for knapsack和这里recursive knapsack）

c++ 实现在我的核心 i7 @3Ghz 上测量 ~20us

于 2015-05-02T10:33:32.520 回答