作者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/m.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