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