作者sate1128 (小夯夯)
看板Prob_Solve
标题[问题] 最佳运费的问题
时间Wed Aug 23 11:13:28 2017
最近小弟在研究一个运费的问题卡关很久
题目大概是有2吨车、5吨车、10吨车
载一趟的运费分别是850、1600、3000
货物有
A:17吨 B:21吨 C:18吨 D:14吨 E:7吨
不同的货可以并车，多载一种货加收300元
但最多只能载三种货
请问怎样的出车组合运费最低？
-
这是一个例子，但最终目的是要写成一个通解
车子、运费、货物、并车次数都会是变数
-
我的想法是超过10吨的货都先用10吨车载
建立两个表（两个货一定并车运费最低的组合
和三个货一定并两次车运费最低的组合）
所以这两个表的栏位就会是总重2~18吨、3～27吨
http://imgur.com/T3ielJ6
这是我用手算的2～18吨表(总重3比较特别 可以不并车）
最後再从除以10之後的货物中挑出最佳解(目前只想到穷举挑法）
-
可是我目前遇到的困难卡在建表
感觉跟ＤＰ很相似（换硬币问题）
可是硬币问题是数量刚刚好
但这个问题车的载重量可能大於货物总重
所以不知道怎麽列出各种组合再算运费
请问有没有人有想法建表或是整个问题有别的解法
感恩
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 114.32.177.2
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Prob_Solve/M.1503458011.A.AE8.html
1F：推 LPH66: 看起来像是 bin packing problem? 08/23 17:50
2F：→ sate1128: 好像不太一样 车子有多个容量而且要考虑并车费 08/24 10:10
3F：推 FRAXIS: 但是 DP 为什麽不能用? 08/24 10:59
4F：推 FRAXIS: 我有一点看不懂问题 假设有两个 D 货物 各用一台 10 吨车 08/24 11:51
5F：→ FRAXIS: 因为 D > 10 吨 所以各有剩下一些没装的货 08/24 11:51
6F：→ FRAXIS: 这两个剩下的货物（都是D）拼在一起 需要加钱吗？ 08/24 11:53
7F：→ sate1128: Dp 应该可以 可是我卡住了QQ 08/24 12:20
8F：→ sate1128: 如果是你刚刚说的例子 他一开始就会是D:34吨 08/24 12:21
9F：→ yoco: 问细节：请问五吨车是上限五吨吗？还是下限？那上限是多少？ 10/15 20:22
10F：→ yoco: 懂了没事 XD 10/15 20:23