Re: [問題] 三位探險家的糧食補給

看板puzzle (益智遊戲 - 數獨,拼圖,推理,西洋棋)作者walkwall (會走路的牆)時間15年前 (2010/04/30 19:36)推噓1(1推 0噓 1→)

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

◎補充思考：若十二天旅程當中，只有一天早上可以讓挑夫返回基地，則最少需要　　　　　　　雇用幾位挑夫？又，該在旅程中第幾天早上讓挑夫返回基地？ ----------------------------------------------------------------------- 　如果中途只能讓挑夫回家一次，則問題變成兩個變數。令回家那次走掉的挑夫有 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包糧食。 -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 140.117.169.167