最近小弟在研究一個運費的問題卡關很久
題目大概是有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之後的貨物中挑出最佳解(目前只想到窮舉挑法）
-
可是我目前遇到的困難卡在建表
感覺跟ＤＰ很相似（換硬幣問題）
可是硬幣問題是數量剛剛好
但這個問題車的載重量可能大於貨物總重
所以不知道怎麼列出各種組合再算運費
請問有沒有人有想法建表或是整個問題有別的解法
感恩