[問題] 最佳運費的問題
看板Prob_Solve (計算數學 Problem Solving)作者sate1128 (小夯夯)時間7年前 (2017/08/23 11:13)推噓3(3推 0噓 7→)留言10則, 4人參與討論串1/1
最近小弟在研究一個運費的問題卡關很久
題目大概是有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
推
08/23 17:50, , 1F
08/23 17:50, 1F
→
08/24 10:10, , 2F
08/24 10:10, 2F
推
08/24 10:59, , 3F
08/24 10:59, 3F
推
08/24 11:51, , 4F
08/24 11:51, 4F
→
08/24 11:51, , 5F
08/24 11:51, 5F
→
08/24 11:53, , 6F
08/24 11:53, 6F
→
08/24 12:20, , 7F
08/24 12:20, 7F
→
08/24 12:21, , 8F
08/24 12:21, 8F
→
10/15 20:22, , 9F
10/15 20:22, 9F
→
10/15 20:23, , 10F
10/15 20:23, 10F
Prob_Solve 近期熱門文章
PTT數位生活區 即時熱門文章
