[問題] 最佳運費的問題

[sate1128 (小夯夯)]

最近小弟在研究一個運費的問題卡關很久

題目大概是有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://www.ptt.cc/bbs/Prob_Solve/M.1503458011.A.AE8.html
推 LPH66: 看起來像是 bin packing problem?
→ sate1128: 好像不太一樣  車子有多個容量而且要考慮併車費
推 FRAXIS: 但是 DP 為什麼不能用?
推 FRAXIS: 我有一點看不懂問題 假設有兩個 D 貨物 各用一台 10 噸車
→ FRAXIS: 因為 D > 10 噸 所以各有剩下一些沒裝的貨
→ FRAXIS: 這兩個剩下的貨物（都是D）拼在一起 需要加錢嗎？
→ sate1128: Dp 應該可以  可是我卡住了QQ
→ sate1128: 如果是你剛剛說的例子  他一開始就會是D:34噸
→ yoco: 問細節：請問五噸車是上限五噸嗎？還是下限？那上限是多少？
→ yoco: 懂了沒事 XD