搬石头

aimisiyou

有  n 个人员，提举力分别为F1, F2, …, Fn。
有 m 块石头，重量分别为G1, G2, …, Gm。
将全体人员分为 m 组（可以有空组）来搬石头，
第 k 组合力大于等于Gk时就能搬动第 k 块石头。
如何分组，使能搬动的石头总重量达到最大？
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}

aimisiyou

开始时想到贪心算法。
将石头由大到小排序，依次配组员，使合力刚好等于或稍大于石头重量，最后剩下几人的合力，找一个刚好比其小的石头，分配完成。
尝试过程如下：
75+45+20=140>139
82+51+1=134
67+37+13=117
49+35+9=93
剩下的29+25+17+6+3=80<89，跳过
29+25+17+6=77>74.
剩余 3 没有用了，其余石头空组。
能搬动的石头总重为139+134+117+93+74=557。

这样分组，74的组冗余人力稍大，最后一组人力3白白浪费了。
假如没有74，则配29+25+17=71>69，最后一组6+3浪费更多，
而把他们编入前面的组或可抬起更大的石块。
可见贪心算法不是总能找到最优解。
有没有更好的算法？

aimisiyou

找到比557更好的结果。

aimisiyou

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

王守恩

F={1,3,6,9,13,17,20,25,29,35,37,45,49,51,67,75,82}=564
先找564，次找563,562,561,560,.....
G={48,57,69,74,89,93,117,134,139}=820
G-F=256=139+117=139+69+48=134+74+48=93+89+74
即F=G-(G-F)=564是可能有的。

aimisiyou

王守恩 发表于 2019-12-18 07:32
F={1,3,6,9,13,17,20,25,29,35,37,45,49,51,67,75,82}=564
先找564，次找563,562,561,560,.....
G={48,57 ...

反向推出哪些石头可以不搬，是个好思路。

markfang2050

程序呢？

aimisiyou

markfang2050 发表于 2019-12-18 20:59
程序呢？

就是在讨论有什么好算法啊？