大概是背包问题的衍生，背包问题是有 N 件物品和一个容量为 V 的背包。第 i 件物品的重量是 c[i]，价值是 w[i]。求解将哪些物品装入背包可使价值总和最大。
我这边需求是有 N 件物品，每件物品对应不同的数量和大小，有 X 种类型的柜子，柜子可以多台组合，柜子里格口大小均可能不同，不同的柜子成本不同，计算能将所有物品装入柜子且机器成本最低的方案。
因为是工作上遇到的需求还需要结合业务场景讲解，会付费给大佬，给出思路即可，不求代码实现，麻烦有兴趣的大佬加下我微信：Q2VuZXJpaQ==
• 请不要在回答技术问题时复制粘贴 AI 生成的内容
This topic created in 1471 days ago, the information mentioned may be changed or developed.
 |
dwlovelifeOct 25, 2022
1
是妹子么
|
 |
nulIptrOct 25, 2022
2
抛个砖，如果是工业或是商业解决方案的话可能不是一个真正纯动态规划问题
古时候在老东家做简单的 aps ，就是有工单人员设备日历，自动排程的问题，看似是动态规划，但是限制条件太多了导致最后发现还是先找最大权重的条件暴力模拟简单。。。 |
 |
3
@dwlovelife 是的，JAVA 后端
|
 |
zhaorunzeOct 25, 2022
4
可以看看美团巨佬写的关于外卖配送的博客，不只是学习算法，还有别人整理的模型，对问题的定义都可以学习学习。
工程级别的算法，不只是要定义问题抽象模型解决问题，还要有仿真模型哦，不然你都没法证明你的算法是有效率的。 |
|
5
@nulIptr 这点我也有感觉，这个需求也有一定的限制，我对算法的研究程度不深，所以想问下其他人能否用动态规划求解，如果没办法的话，用暴力求解那如何优化复杂度，这都是我想咨询的。
|
 |
6
光听需求，可能不是动规。
动规是要能做到局部最优解，然后往上挂状态转移方程。 这里假如已经用 x 个柜子装了 y 件物品，再装入一个新物品的时候，前一个局部解可能就不是最优解了。 比如 y 件物品正好塞满一个柜子，y+1 件商品变成一个柜子+一个小柜子，但是低成本方案可能是平均拆成两个中柜子。 |
2 |
paopjianOct 25, 2022
7
试试用 utools?https://developers.google.com/optimization/bin/bin_packing 有现成的解决方案
|
 |
asLw0P981N0M0TCCOct 25, 2022
9
还真有人在讨论算法 我先加微信再说 嘿嘿
|
 |
zhoudaiyuOct 25, 2022
10
@zhaorunze #4 大佬 美团的哪篇博客啊 https://tech.meituan.com/2020/02/20/meituan-delivery-operations-research.html 这个么？
|
 |
YVAN7123Oct 25, 2022
11
@dwlovelife 你问到重点了 ~ 钱不钱不重要
|
|
dwlovelifeOct 25, 2022
12
@YVAN7123 哈哈，帮兄弟们问的
|
 |
xuqdOct 25, 2022
13
OptaPlanner, 这个好像可以处理复杂规划
|
|
dwlovelifeOct 25, 2022
14
妹子给你推荐一个东西 叫规则引擎 这种业务代码 单纯的算法可以完成 但是代码耦合相当高 正常这种玩意如果是我做 我建议把规则放在存储层 然后指定规则模版 拿规则引擎去撞
|
 |
aeronOct 25, 2022
15
去年做 APS 时研究过，最后扔给 ortools 算了
|
 |
optionalOct 25, 2022 via iPhone
16
这是个整数优化问题，上 ortools ，复杂的话再来点启发式算法
|
 |
XSDoOct 25, 2022
17
动态规划的变种，如果看动态规划的算法是解决不了问题的，要做调整才行的
|
 |
MoYi123Oct 25, 2022
19
十有八九是个 np 问题, 建议凭经验直接搞个启发式得了.
|
 |
helloworld000Oct 25, 2022
20
好奇问一下这种 hash 微信号怎么恢复成真正的号码？
|
 |
renmuOct 25, 2022 via Android
21
钱不钱不重要，我们可以线下仔细沟通业务场景和算法（狗头）
|
 |
bruce0Oct 25, 2022
22
我原本还想加个 wx,可是我大概率也给不出好的解决方案, 还是别这么不要脸了😢
|
 |
23
|
 |
iOCZOct 25, 2022
24
偶然点开楼主的回帖，有个帖子让我的心沉了下去。。。
|
 |
nekonekoOct 25, 2022
25
@SunsetShimmer #23 穷举的话 64 的 7 次方大概, 4 万亿次计算...
|
 |
berg223Oct 26, 2022 via Android
26
考虑现实意义，格口更大的柜子装 1 立方米的平均成本是否一定比格口小的成本低呢
|
 |
c0xt30aOct 26, 2022
27
有测试数据么？发一组上来尝试下。不习惯加陌生人微信。
|
 |
dayeye2006199Oct 26, 2022
28
我有个大规模整数优化的博士学位，可以接受咨询
|
 |
caixiangyu17Oct 26, 2022
29
@msg7086 感觉你最后的例子好像有一点问题，y+1 的解法不是吧 y 取出最优解加上一个。
y+1 的解法是整合 y+1, (y-1)+2, (y-2)+3, (y-3)+4.....的所有解，取最优，所以你举着个例子正好是一个动态规划的方案。 |
 |
buliuguOct 26, 2022
30
optaplanner
|
|
msg7086Oct 26, 2022 via Android
31
@caixiangyu17 不对，你这里的 y-1 y-2 不是单个值，他们本身就是一个集合（取出任何一个或两个物品后的价值的最大值），所以会迅速放大计算量，失去动规的意义。
|
|
32
目前问题未解决，由于 deadline 逼近，希望有大佬能帮忙解决。目前我的困难是没办法根据需求抽象出计算模型，不求具体实现，提供抽象数学模型和可实现思路，预算 500 ，个人支付，有兴趣的老哥可以加下我。
|
 |
guyeuOct 27, 2022
33
看需求感觉不像是个动态规划问题，楼主有解法之后踢我一下，学习一个
|
Select Language