三位探險家的糧食補給 - 拼圖

◎補充思考：若十二天旅程當中，只有一天早上可以讓挑夫返回基地，則最少需要
　
　　　　　　雇用幾位挑夫？又，該在旅程中第幾天早上讓挑夫返回基地？

-----------------------------------------------------------------------

　如果中途只能讓挑夫回家一次，則問題變成兩個變數。

令回家那次走掉的挑夫有 A 位，留下的挑夫有 B 位

先考慮 B 位挑夫留下來，所攜帶最大糧食能與三位探險家撐過的天數 D(B)，取整數


D(B) = 10B / (B + 3)
= (10B + 30 - 30) / (B + 3) = 10 - 30 / (B + 3)

可得 D(1) = 2, D(2) = 3, D(3) = 5, D(5) = 6, D(7) = 7,

D(12) = 8, D(27) = 9, D(無限大) = 10 為剩餘該天數的最佳 B 值



1.第一天的時候所攜帶的糧食總數為 10 * ( A + B )

2.第一天到派挑夫走的那天，共計消耗糧食　( 12 - D(B) ) * ( A + B + 3 )

3.派挑夫走的那一天，至少應留下糧食　D(B) * ( B + 3 )

應滿足　1. - 2. >= 3.　的關係式

　可推得，當 B = 1 的時候，關係式 -> 無解 A + B = 無解
　　　　　當 B = 2 的時候，關係式 -> A >= 20 A + B = 22
當 B = 3 的時候，關係式 -> A >= 14 A + B = 17
當 B = 5 的時候，關係式 -> A >= 12 A + B = 17
當 B = 7 的時候，關係式 -> A >= 10 A + B = 17
當 B = 12 的時候，關係式 -> A >= 10 A + B = 22
當 B = 27 的時候，關係式 -> A >= 12 A + B = 39

所以不論是第六天 or 第七天 or 第八天的早上叫挑夫走，都是最佳解挑夫17人

然而三者所需消耗的總糧食 分別為 170, 168, 170

所如果也考慮攜帶糧食數量的最佳化的話，應該是一開始雇 17 人，於第7天上午

送走 12 人，留下 5 人，共需要168包糧食。

--