Re: [其他] 載貨問題
: 如題，想問一下板上大大這題該如何解？
: 謝謝
令 w,t,m 分別為 大、中、小 運輸機飛往伊拉克的次數
Lemma 1: 如果飛行次數分別為 w,t,m ，則需要的天數是
max { 2*ceiling(w/3) -1 , 2*ceiling(t/5) -1, 2*ceiling(m/5)-1}
= 2 max { ceiling(w/3), ceiling(t/5), ceiling(m/5)} - 1
上面那個 ceiling(x) 為 大於等於 x 的最小整數
這個是因為基地一天可以往伊拉克分別出 3大、5中、5小 運輸機的關係。
比如說：你要分別出 10, 6 ,5 次 大中小 運輸機往伊拉克飛
10 次大運輸機往伊拉克，要 2ceiling (10/3) -1 = 9 天
6 次大運輸機往伊拉克，要 2ceiling (4/5) -1 = 3 天
5 次大運輸機往伊拉克，要 2ceiling (5/5) -1 = 1 天
那整個過程就是 9 天
Lemma 2: 假設大中小運輸機飛往伊拉克次數為 w,t,m 。能否把 30, 100, 500 貨物
運往伊拉克的充要條件為滿足下列不等式
2w + t >= 30 ,
(2w + t -30)*3 + 2w + 2t + 2m >= 100 ,
[(2w + t -30)*3 + 2w + 2t + 2m - 100]*5 + 15w + 10t + 15m >= 500
我們先看大型貨物的部分 大運輸機 w 次 和 中運輸機 t 次往伊拉克，
最多可以運 2w + t 個大型貨物，這個運輸量要至少 30，所以有 2w + t >= 30
好，現在我們確認大型貨物可以送完了，那就來看看在確定能運完30個大型貨物後，
最多可以運個多少中型貨物
w,t,m 原本就可以運 2w+2t+2m 個中型貨物，
而原來可以運 2w+t 個大型貨物，扣除30個之後，因為貨物材積 1大 = 3中，
所以最多可以運 (2w + t -30)*3 + 2w + 2t + 2m 個中型貨物，
而中型貨物有100個，所以需要 (2w + t -30)*3 + 2w + 2t + 2m >= 100
第三個不等式的情況式類似的
好，總和 Lemma 1 和 Lemma 2
這問題變成是在找
min 2 max { ceiling(w/3), ceiling(t/5), ceiling(m/5)} - 1
(w,t,m) in D
其中 D 是所有滿足 Lemma 2 裡面不等式的 w,t,m
好，那這要怎麼找呢？
先看看 Lemma2 裡面不等式，你一眼看下去應該感覺得出，
單指想要滿足不等式的話， (w,t,m) 三個數字是越大越好
但我們在找到夠大的 (w,t,m) 同時，又希望
max { ceiling(w/3), ceiling(t/5), ceiling(m/5)} 越小越好
這邊有一個關鍵是， max { ceiling(w/3), ceiling(t/5), ceiling(m/5)} = n 等價於
w <= 3n 且 t<= 5n 且 m <=5n
所以我們其實想要一個最小的 n 讓 w=3n, t=5n, m = 5n 滿足 Lemma 2 裡面的不等式。
問題可以改寫成
min 2*n-1
(3n,5n,5n) in D
(3n,5n,5n) 代入 Lemma 2 的不等式會分別是
11n - 30 >= 0
59n - 190 >= 0
99n - 290 >= 0
找出來最小的 n = 4，所以可以在 2*4-1 =7 天內完成
這個結果也可以直接反向檢驗：
7天內，你可以往伊拉克送出 12班大運輸機, 20班中運輸機, 20班小運輸機
6天呢？ 這個天數沒有道理，因為會6天表示至少有一個班機摸魚1天，不可饒恕
5天內，你可以往伊拉克送出 9班大運輸機，15班中運輸機，15班小運輸機
這個運輸量，大型貨物運完你只會剩下 87個中型貨物運輸量，不足100
--
角卷綿芽首次個人Live： Watame Night Fever!! in Zepp Tokyo
https://pbs.twimg.com/media/E9PIgJ7VkAUExEa.jpg
入場時間：台灣時間 2021/10/12 (星期二) 下午 4:30
官網購票連結：https://watame1stlive.hololive.tv/tickets/
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 98.45.135.233 (美國)
※ 文章網址: https://www.ptt.cc/bbs/Math/M.1631164410.A.35B.html
※ 編輯: arrenwu (98.45.135.233 美國), 09/09/2021 13:18:00
討論串 (同標題文章)
完整討論串 (本文為第 2 之 2 篇)：
其他
-1
4