全部版块 我的主页
论坛 提问 悬赏 求职 新闻 读书 功能一区 悬赏大厅
1032 3
2019-05-02
悬赏 2000 个论坛币 未解决
要求:现有一组数据,共有N个数,要求将这些数分组,使得每组的各数之和不大于M,现在要求出最小的分组数目及分组情况。急需求解思路以及程序代码!!!
谢谢大家
二维码

扫码加我 拉你入群

请注明:姓名-公司-职位

以便审核进群资格,未注明则拒绝

全部回复
2019-5-4 05:17:21
集装优化是一个 NP-complete 问题,只能使用穷举法来求最优解了。

那么思路就非常明确了:
第一步,考虑将这N个数放入N个空间无限的箱子,将会有N平方种放法;
第二步,对于N平方中的任意一种放法,验证每个箱子内的各数之和不大于M,在此基础上计算不是空着的箱子数目;
第三步,N平方种放法中使用箱子最少的就是所求答案。
附件是我自己写的 Python 代码,使用的3个例子是参考 GeeksforGeeks 上的。

感觉第一步穷举的步骤会有更好的方法?欢迎大家继续讨论,也请楼主先采纳我的答案:)
附件列表

bin_packing_problem.txt

大小:1001 Bytes

只需: 2000 个论坛币  马上下载

二维码

扫码加我 拉你入群

请注明:姓名-公司-职位

以便审核进群资格,未注明则拒绝

2019-5-5 13:22:59
1)N数组求和除M取整+1得到最小分组数C;

2)然后把N数组从小到大排序为N1,N2。。。。Ni,分大小数两组,当N为偶数,大小数组各为N/2个,当N为奇数,小数理组为(N-1)/2+1个,大数组为(N-1)/2个;小数组升序排为数列Ai,大数组倒序排为数列Bi
3)用Ai+Bi与M比较分组,以此类推,用循环语句实现即可
二维码

扫码加我 拉你入群

请注明:姓名-公司-职位

以便审核进群资格,未注明则拒绝

2019-5-5 22:23:39
dryear 发表于 2019-5-4 05:17
集装优化是一个 NP-complete 问题,只能使用穷举法来求最优解了。

那么思路就非常明确了:
感谢
二维码

扫码加我 拉你入群

请注明:姓名-公司-职位

以便审核进群资格,未注明则拒绝

相关推荐
栏目导航
热门文章
推荐文章

说点什么

分享

扫码加好友,拉您进群
各岗位、行业、专业交流群