搬石头

aimisiyou

有N个人，力气值分别为F1，F2……FN，有M个石头，重量值分别为G1、G2……GM，F之和大于或等于G时就能搬动石头，如何分配人员，使能搬动的石头重量达到最大？
F={1,3,6,9,13,17,20,25,29,35,37,45,49,51,67,75,82}
G={48,57,69,74,89,93,117,134,139}
开始时想到贪心算法，即将石头质量由大到小排序，然后挑选人使其合力刚好等于石头量或稍大于石头重量，最后剩下几人的合力，找一个刚好比其小的石头，分配完成。
尝试过程如下：
75+45+20=140>139
82+51+1=134
67+37+13=117
49+35+9=93

剩下的29+25+17+6+3=80<89
离80最近且小于80的是74.
故此人员分配能搬动的石头总重为139+134+117+93+74=557。
可以想象，此种算法不是很好（比如没有74和69的石头，将会导致人力浪费严重），即大的抬不起，小的太不值或没有小的可抬的尴尬场面。
有没有好的算法？

aimisiyou

通过尝试法找到更好的结果560.还不知道是不是最优解。没想到随机编的一些数据，算起来还好复杂。开始时还以为数据会运算很简单，看来这组随机数据给了我意外惊喜。感觉如果能实现找到较好近优解的算法话，其算法应该很复杂。

刀羊

这个可以试试插件 规划求解

aimisiyou

刀羊 发表于 2019-12-18 20:12
这个可以试试插件 规划求解

怎么设置在一块区域内（比如A1B1:A4B5）必须包含一些数目（如1 2 3 4 5 ）的限制条件？

丢丢表格

刀羊 发表于 2019-12-18 20:12
这个可以试试插件 规划求解

此题用规划求解，今一上午都没运行成功，因为计算量太大了。

要是用 VBA 做，我的四核机  也许得用 1天时间计算 。（太可怕了）

=(6^6)^9  的计算，烧机子呀

yjh_27

即使暴力计算，也就10^17次

aimisiyou

yjh_27 发表于 2019-12-19 13:19
即使暴力计算，也就10^17次

按每秒30亿次计算，也要10.5年。有没有什么实用有效的算法，可以在较短时间内找到近优解？

koala219

有点意思哈。这么算呢？

yjh_27

aimisiyou 发表于 2019-12-19 13:59
按每秒30亿次计算，也要10.5年。有没有什么实用有效的算法，可以在较短时间内找到近优解？

1 按 0.9~1倍的合力，找石头可能组合，
2 按各组合（按重量和倒序），找人力分配
3找到分配方案即最大

aimisiyou

koala219 发表于 2019-12-19 14:54
有点意思哈。这么算呢？

数据可以变，但算法不离其宗。