Re: [問題] 最低運輸費用

看板puzzle (益智遊戲 - 數獨,拼圖,推理,西洋棋)作者stimim (qqaa)時間13年前 (2012/07/12 10:23)推噓0(0推 0噓 0→)

留言0則, 0人參與討論串3/3 (看更多)

※ 引述《cj6u40 (阿克 \⊙▽⊙/)》之銘言：　　最低運輸費用　 ┌─────────────────────────────────────┐ │◎Ｑuestion　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　 │ │　「易上路」是一家全國性的汽車租借公司，在各地主要有七個租借中心。以下是　│ │　七處目前所有的車輛過剩或不足情形：　　　　　　┌─┬─┬─┬─┬─┐　　│ │　Ａ過剩9輛、Ｂ過剩6輛、Ｃ過剩8輛；　　　　　　 │　│Ｐ│Ｑ│Ｒ│Ｓ│　　│ │　Ｐ不足5輛、Ｑ不足7輛、Ｒ不足3輛、Ｓ不足8輛。　├─┼─┼─┼─┼─┤　　│ │　　　　　　　　　　　　　　　　　　　　　　　　│Ａ│60│20│50│40│　　│ │　為了達成供需平衡，現在公司決定重新布局，以過　├─┼─┼─┼─┼─┤　　│ │　剩的車輛填補不足的部分。而各地之間一輛車的運　│Ｂ│40│50│30│80│　　│ │　輸了費用如右表所列，如Ａ→Ｐ需要60英鎊。　　　├─┼─┼─┼─┼─┤　　│ │　欲使運費最低，公司應如何安排？此時運費為何？　│Ｃ│30│40│70│50│　　│ │　　　　　　　　　　　　　　　　　　　　　　　　└─┴─┴─┴─┴─┘　　│ │◎Ａnswer　　　　　　　　　　　　　　　　　　　　　　　（單位：英鎊）　　 │ │　答案請開燈：790元　　　　　　　　　　　　　　　　　　　　　　　　　　　 │ └─────────────────────────────────────┘ 　※題目出處：《數學遊樂園之妙想天開》（牛頓，2002）第64、65、135、136頁。上一篇說的是原理，現在則是實際的解一次看看，因為 cost 都是 10 的倍數，所以在下面的過程中，都直接用 cost/10 來算。和剛剛不一樣的是，X = {A, B, C}, Y = {P, Q, R, S} 的車輛狀況都不是多或少一輛，理論上我們要把他們變成 23 * 23 的表格來解，可是這裡面有很多重複的東西，所以，我們只有在必要的時候才把 X 和 Y 更細分。一開始的表格變這樣 5P(3) 7Q(2) 3R(3) 8S(4) 9A(0) 3 0 2 0 6B(0) 1 3 0 4 8C(0) 0 2 4 1 數字代表的是那一個行或列其實有數台車，在匹配的時候，比如說，CP 可以產生配對，可是只有 5 對，有 3 個 C 會剩下，所以我們要把 C 分成 5C 和 3C 兩列。並用 0 代表被匹配的 0 5P(3) 7Q(2) 3R(3) 2S(4) 6S(4) 7A(0) 3 0 2 0 0 2A(0) 3 0 2 0 0 3B(0) 1 3 0 4 4 3B(0) 1 3 0 4 4 5C(0) 0 2 4 1 1 3C(0) 0 2 4 1 1 可以發現並沒有完美匹配 (我們只匹配了 5 + 7 + 3 + 2 = 17 個 0) ，所以要找出 Z ， (事實上，會有 |Z| = 17 也就是剛剛被匹配的 0 的個數) 結果是： 5P(3) 7Q(2) 3R(3) 2S(4) 6S(4) 7A(0) 3 0 2 0 0 2A(0) 3 0 2 0 0 3B(0) 1 3 0 4 4 3B(0) 1 3 0 4 4 5C(0) 0 2 4 1 1 3C(0) 0 2 4 1 1 Z = {7A(0), 2A(0), 5P(3), 3R(3)} |Z| = 7 + 2 + 5 + 3 = 17 e = 1 現在要更新表格： 5P(3) 7Q(3) 3R(3) 2S(5) 6S(5) 7A(-1) 4 0 3 0 0 2A(-1) 4 0 3 0 0 3B( 0) 1 2 0 3 3 3B( 0) 1 2 0 3 3 5C( 0) 0 1 4 0 0 3C( 0) 0 1 4 0 0 尋找匹配： 5P(3) 7Q(3) 3R(3) 2S(5) 3S(5) 3S(5) 7A(-1) 4 0 3 0 0 0 2A(-1) 4 0 3 0 0 0 3B( 0) 1 2 0 3 3 3 3B( 0) 1 2 0 3 3 3 5C( 0) 0 1 4 0 0 0 3C( 0) 0 1 4 0 0 0 被匹配的 0 有 5 + 7 + 3 + 2 + 3 = 20 個 5P(3) 7Q(3) 3R(3) 2S(5) 3S(5) 3S(5) 7A(-1) 4 0 3 0 0 0 2A(-1) 4 0 3 0 0 0 3B( 0) 1 2 0 3 3 3 3B( 0) 1 2 0 3 3 3 5C( 0) 0 1 4 0 0 0 3C( 0) 0 1 4 0 0 0 Z = {7A, 2A, 3C, 5C, 3R} |Z| = 20 e = 1 更新表格： 3P(4) 2P(4) 7Q(4) 3R(3) 2S(6) 6S(6) 7A(-2) 4 4 0 4 0 0 2A(-2) 4 4 0 4 0 0 3B( 0) 0 0 1 0 2 2 3B( 0) 0 0 1 0 2 2 2C(-1) 0 0 1 5 0 0 6C(-1) 0 0 1 5 0 0 匹配完成， 3 B->P, 2 C->P, 7 A->Q, 3 B->R, 2 A->S, 6 C->S 花費為 (4*5 + 7*4 + 3*3 + 8*6 + 9*(-2) + 6*(0) + 8*(-1)) * 10 = 790 -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 60.250.111.124 ※ 編輯: stimim 來自: 60.250.111.124 (07/12 12:26)