搬石头

aimisiyou · 发表于 2019-12-17 22:50:48

马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。

您需要登录才可以下载或查看，没有账号？立即注册

×

本帖最后由 aimisiyou 于 2019-12-18 07:23 编辑

有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}

aimisiyou · 发表于 2019-12-17 23:02:36

本帖最后由 aimisiyou 于 2019-12-17 23:17 编辑

开始时想到贪心算法，即将石头质量由大到小排序，然后挑选人使其合力刚好等于石头量或稍大于石头重量，最后剩下几人的合力，找一个刚好比其小的石头，分配完成。
尝试过程如下：
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 · 发表于 2019-12-17 23:12:24

找到一个比557更好的解559。

aimisiyou · 发表于 2019-12-17 23:14:27

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

aimisiyou · 发表于 2019-12-19 20:21:07

求助EXCEL高手，给出百分百完美答案！！！

账号		自动登录	找回密码
密码			立即注册

[原创] 搬石头

马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。