搬石头

zopey

石头跟背包的想法 相反

astupig

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

astupig

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

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

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

aimisiyou

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

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

astupig

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)那么所在石头分配的力气值之和要大于这个石头的重量。

yjh_27

163个最优分配方案，最优解是564

1 按 人力的合力，找石头可能石头组合，有4种组合
2 按 各石头重量 ，找人力可能人力组合
3 按石头组合索引 各人力组合 进行排列，无交集的即为可行分配方案

504373

有意思的题目...

aoe1981

感觉这个问题和“一维下料”还不一样，似乎是相反的。

我把“力气”当零件，把“石头”当原料，在下料问题中，零件组合长度小于等于原料，但这个搬石头的问题中，力气组合大于等于石头。

本例中的数据恰好可以相等，故而撞出了结果，如果数据变化了，肯定不行的……

aoe1981

好像还有两种组合:







说不定还有其他的。