搬石头

zopey · 发表于 2019-12-19 17:07

石头跟背包的想法相反

astupig · 发表于 2019-12-19 17:26

本帖最后由 astupig 于 2019-12-19 17:36 编辑

最优解是564. 设定两组变量，一组用来记录是否搬石头（if moved); 另外一组是所在的力气值是否分配到对应的石头。
增加约束条件就可以了。这个是比较简单线性规划问题。对了，我用Open Solver， Excel的插件，大多时候比Solver快几十倍以上。这个求解大概3秒就出结果了。

astupig · 发表于 2019-12-19 17:34

丢丢表格发表于 2019-12-18 20:59
此题用规划求解，今一上午都没运行成功，因为计算量太大了。

要是用 VBA 做，我的四核机也许得用 1 ...

自带的规划求解速度很慢的，要用开源求解器。推荐Open Solver. Bing搜索一下就有。www.opensolver.org

aimisiyou · 发表于 2019-12-19 23:54

astupig 发表于 2019-12-19 17:26
最优解是564. 设定两组变量，一组用来记录是否搬石头（if moved); 另外一组是所在的力气值是否分配到对应 ...

能详细说说算法流程么？一般的线性规划结果是一维向量，这里的结果是二维向量。

astupig · 发表于 2019-12-20 08:19

aimisiyou 发表于 2019-12-19 23:54
能详细说说算法流程么？一般的线性规划结果是一维向量，这里的结果是二维向量。

这个参考了Network Modeling的做法，所以有点像二维向量。
这个在线性规划里面叫做混合整数规划，就是有多组变量协同工作，用一组变量来约束另外一组变量。

比如要决定决定搬哪个石头这组变量(if moved), 总共9个（binary二进制)，用来给目标函数服务的，因为重量值G只是数值（常数），所以要一组变量来做决定。

而那个二维变量是用来规划石头用哪些力气值来搬。比如57，就用3+9+45, 那么在对应的位置填上1，然后SUMPRODUCT. 其实这个跟财务凑数（从一组数里面找出总和是某个目标数的问题）是非常相似的, 可以看作是二维财务凑数，不过让程序决定能否凑完所有的数（也就是石头）。

约束方面也是要仔细考虑的：
1 每个力气值只能用一次，就有L列小于等于N列这个约束；
2 要if moved这组变量跟那个二维变量的总和进行“联动”，就是要决定搬这个石头(if moved=1)那么所在石头分配的力气值之和要大于这个石头的重量。