ExcelHome技术论坛

 找回密码
 免费注册

QQ登录

只需一步,快速开始

EH搜索     
EH技术汇-专业的职场技能充电站 妙哉!函数段子手趣味讲函数 Excel服务器-会Excel,做管理系统 Excel Home精品图文教程库
Excel不给力? 何不试试FoxTable! Excel 2016函数公式学习大典 Office知识技巧免费学 打造核心竞争力的职场宝典
300集Office 2010微视频教程 Tableau-数据可视化工具 精品推荐-800套精选PPT模板,点击获取 ExcelHome出品 - VBA代码宝免费下载
你的Excel 2010实战技巧学习锦囊 欲罢不能, 过目难忘的 Office 新界面 Excel VBA经典代码实践指南
查看: 1014|回复: 28

[讨论] 搬石头

[复制链接]

TA的精华主题

TA的得分主题

发表于 2019-12-17 23:32 | 显示全部楼层 |阅读模式
本帖最后由 aimisiyou 于 2019-12-17 23:34 编辑

有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的石头,将会导致人力浪费严重),即大的抬不起,小的太不值或没有小的可抬的尴尬场面。
有没有好的算法?
m1.png

TA的精华主题

TA的得分主题

 楼主| 发表于 2019-12-17 23:37 | 显示全部楼层
通过尝试法找到更好的结果560.还不知道是不是最优解。没想到随机编的一些数据,算起来还好复杂。开始时还以为数据会运算很简单,看来这组随机数据给了我意外惊喜。感觉如果能实现找到较好近优解的算法话,其算法应该很复杂。
m4.png

TA的精华主题

TA的得分主题

发表于 2019-12-18 20:12 | 显示全部楼层

TA的精华主题

TA的得分主题

 楼主| 发表于 2019-12-18 20:27 | 显示全部楼层
刀羊 发表于 2019-12-18 20:12
这个可以试试插件 规划求解

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

TA的精华主题

TA的得分主题

发表于 2019-12-18 20:59 | 显示全部楼层
本帖最后由 丢丢表格 于 2019-12-18 21:02 编辑
刀羊 发表于 2019-12-18 20:12
这个可以试试插件 规划求解

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

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

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




TA的精华主题

TA的得分主题

发表于 2019-12-19 13:19 | 显示全部楼层

TA的精华主题

TA的得分主题

 楼主| 发表于 2019-12-19 13:59 | 显示全部楼层
yjh_27 发表于 2019-12-19 13:19
即使暴力计算,也就10^17次

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

TA的精华主题

TA的得分主题

发表于 2019-12-19 14:54 | 显示全部楼层

TA的精华主题

TA的得分主题

发表于 2019-12-19 15:21 | 显示全部楼层
aimisiyou 发表于 2019-12-19 13:59
按每秒30亿次计算,也要10.5年。有没有什么实用有效的算法,可以在较短时间内找到近优解?

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

TA的精华主题

TA的得分主题

 楼主| 发表于 2019-12-19 15:21 | 显示全部楼层
您需要登录后才可以回帖 登录 | 免费注册

本版积分规则

关注官方微信,每天学会一个新技能

手机版|关于我们|联系我们|ExcelHome

GMT+8, 2020-4-3 06:54 , Processed in 1.120393 second(s), 28 queries , Gzip On.

Powered by Discuz! X3.4

© 1999-2020 Wooffice Inc.

   

沪公网安备 31011702000001号 沪ICP备11019229号

本论坛言论纯属发表者个人意见,任何违反国家相关法律的言论,本站将协助国家相关部门追究发言者责任!     本站特聘法律顾问:徐怀玉律师 李志群律师

快速回复 返回顶部 返回列表