求一个动态规划算法

2023-11-16 22:40:48 +08:00
jiangzm  jiangzm

大概需求是这样的 1 、有 N 个盒子,每个盒子有 50 个针位 2 、有 M 种钻针,每一种钻针数量不定(可以大于 50 ) 3 、同一种钻针需大于 50 才能轮换到其他盒子

给定多种钻针及数量,求使用最少盒子的排放组合?

eg: | 钻针 | 数量 | | ----------- | ----------- | | 1 |5 | | 2 |8 | | 3 |20 | | 5 |44 | | 6 |12 | | 7 |120 | | 8 |10 |

输出 [ [1,1,1,1,1,2,2,2...], [5,5,5,5,5,...] ]

1195 次点击
所在节点   算法  算法
5 条回复
xupefei
xupefei
2023-11-16 22:43:08 +08:00
没看懂,如果一种钻针少于 50 个,那它们必须放在同一个盒子里?
jiangzm
jiangzm
2023-11-16 22:44:42 +08:00
@xupefei 是的
jiangzm
jiangzm
2023-11-16 22:56:56 +08:00
盒子不一定要排满, 最坏的情况就是每一种钻针都是单独的盒子
xupefei
xupefei
2023-11-16 22:57:58 +08:00
1. 把每种数量大于 50 的针拿出 50 的倍数出来,放在单独的盒子里。这样做完后每种针的数量必定小于 50 。
2. 问题简化为了 bin packing ,具体可以在 wikipedia 的页面上找一个近似算法实现一下。
jiangzm
jiangzm
2023-11-16 23:02:07 +08:00
@xupefei 多谢,看了下和装箱问题很接近, 前面一直在查背包问题没找到

这是一个专为移动设备优化的页面(即为了让你能够在 Google 搜索结果里秒开这个页面),如果你希望参与 V2EX 社区的讨论,你可以继续到 V2EX 上打开本讨论主题的完整版本。

https://www.v2ex.com/t/992605

V2EX 是创意工作者们的社区,是一个分享自己正在做的有趣事物、交流想法,可以遇见新朋友甚至新机会的地方。

V2EX is a community of developers, designers and creative people.

© 2021 V2EX