﹝來源﹞
昨天看《美麗境界》一書(第十八章??)，書中寫著nash在 MIT時......，當時盛
行了如下吉普車的後勤問題。
﹝問題﹞
有台吉普車，要橫越2000km的沙漠，但車上所能裝載的汽油量至多可跑 200km。
因此必需如下的來回往返才能橫越沙漠。
先開至50km處，放下供 100km的油箱在此，接著返回裝滿油。
再開至50km處，補充滿，再開至 100km處，放下供 100km的油，再回到出發點。
接著再開至50km處，放下供 100km的油箱在此，接著返回裝滿油。
再開至50km處，補充滿，再開至 100km處，放下供 100km的油，再回到出發點。
此時 100km處有供 200km的油，
第三趟一次開至 100km處，加滿，再往前跑至 150km處，再回來.......
問：若要橫越沙漠，最少要耗掉多少的油量，其方法為何？
(前三次不一定要照我上面所舉的例子)
﹝備註﹞
我不知答案....
關於來源的部份，我現在手邊沒書，只憑印象。
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.112.249.83
※ 編輯: arist 來自: 140.112.249.83 (09/14 09:48)
> -------------------------------------------------------------------------- <
作者: KAEDA (我可沒白遊陰間喔～) 看板: puzzle
標題: Re: 【益智問題】[計算]後勤問題
時間: Sat Sep 14 10:36:32 2002
※ 引述《arist ( 川 )》之銘言：
: ﹝問題﹞
: 有台吉普車，要橫越2000km的沙漠，但車上所能裝載的汽油量至多可跑 200km。
: 因此必需如下的來回往返才能橫越沙漠。
: 先開至50km處，放下供 100km的油箱在此，接著返回裝滿油。
: 再開至50km處，補充滿，再開至 100km處，放下供 100km的油，再回到出發點。
: 接著再開至50km處，放下供 100km的油箱在此，接著返回裝滿油。
: 再開至50km處，補充滿，再開至 100km處，放下供 100km的油，再回到出發點。
: 此時 100km處有供 200km的油，
: 第三趟一次開至 100km處，加滿，再往前跑至 150km處，再回來.......
: 問：若要橫越沙漠，最少要耗掉多少的油量，其方法為何？
: (前三次不一定要照我上面所舉的例子)
很像九連環的東西.....
但現在是40連環??題目並沒說明車上可以載多少油....
看舉例好像是可以跑 100km 的油....
不一樣的是,
九連環的目的要把九個都拆開,這個問題是只要拆第 40 個環....
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.112.68.180
> -------------------------------------------------------------------------- <
作者: arist ( 川 ) 看板: puzzle
標題: Re: 【益智問題】[計算]後勤問題
時間: Mon Sep 16 01:39:48 2002
※ 引述《KAEDA (我可沒白遊陰間喔～)》之銘言：
: ※ 引述《arist ( 川 )》之銘言：
: : ﹝問題﹞
: : 有台吉普車，要橫越2000km的沙漠，但車上所能裝載的汽油量至多可跑 200km。
: : 因此必需如下的來回往返才能橫越沙漠。
: : 先開至50km處，放下供 100km的油箱在此，接著返回裝滿油。
: : 再開至50km處，補充滿，再開至 100km處，放下供 100km的油，再回到出發點。
: : 接著再開至50km處，放下供 100km的油箱在此，接著返回裝滿油。
: : 再開至50km處，補充滿，再開至 100km處，放下供 100km的油，再回到出發點。
: : 此時 100km處有供 200km的油，
: : 第三趟一次開至 100km處，加滿，再往前跑至 150km處，再回來.......
: : 問：若要橫越沙漠，最少要耗掉多少的油量，其方法為何？
: : (前三次不一定要照我上面所舉的例子)
: 很像九連環的東西.....
: 但現在是40連環??題目並沒說明車上可以載多少油....
: 看舉例好像是可以跑 100km 的油....
第一行中 有著寫 可跑200km ?
: 不一樣的是,
: 九連環的目的要把九個都拆開,這個問題是只要拆第 40 個環....
這可比九連環 要複雜的多 不是多在次數 而是難在 折反點
想問的是 如何才耗能最少油 折返點的決定處 要是如何....
過了兩天都沒什麼人回應 我再把題目說清礎些
或者先簡化一下題目 當沙漠長只有400km
採用如下兩種方法 (為了敘述方邊 1L的油當作跑1KM)
; 所剩油量 加油
1.從 0 至 50km 放100L 回 0 ; 50km 100L 200
2.從 0 至100km 放100L 回 0 ;100Km 100L 200
3.再重覆1~2 7次 ;100km 800L 2800
4.從 0 至150km 放100L 回100 ;150km 100L 100km 700L 200
5.從100 至200km 放100L 回100 ;200km 100L 100km 500L 0
6.從100 至150km 放100L 回100 ;150km 100L 100km 300L 200km 100L 0
7.從100 至200km 放100L 回100 ;200km 200L 100km 100 0
8.從100 至400km 0
共耗 3400
; 所剩油量 加油
1.從 0 至 50km 放100L 回 0 ; 50km 100L 200
2.再作1 15次 ; 50km1600L 3000
3.從 0 至100km 放 50L 回 50 ; 50km1550L 100km 50L 200
4.從 50 至100km 放100L 回 50 ; 50km1350L 100km 150L 0
5.再作4 6次 ; 50km 150L 100km 750L 0
6.從 50 至150km 放100L 回100 ;100km 650L 150km 100L 0
7.再100 至150km 放100L 回100 ;100km 450L 150km 200L 0
8.再作7. 2次 ;100km 50L 150km 400L 0
9.從100 至200km 放100L 回150 ;200km 100L 150km 150L 0
8.從150 至400km 到終點 ;200km 50L
共耗 3400
且200km剩50
========
剛試了一些其他分割法 似乎耗油量都更大....
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.112.249.83
> -------------------------------------------------------------------------- <
作者: arist ( 川 ) 看板: puzzle
標題: Re: 【益智問題】[計算]後勤問題
時間: Tue Sep 17 00:48:27 2002
※ 引述《arist ( 川 )》之銘言：
: ※ 引述《KAEDA (我可沒白遊陰間喔～)》之銘言：
: : 很像九連環的東西.....
: : 但現在是40連環??題目並沒說明車上可以載多少油....
: : 看舉例好像是可以跑 100km 的油....
: 第一行中 有著寫 可跑200km ?
: : 不一樣的是,
: : 九連環的目的要把九個都拆開,這個問題是只要拆第 40 個環....
: 這可比九連環 要複雜的多 不是多在次數 而是難在 折反點
: 想問的是 如何才耗能最少油 折返點的決定處 要是如何....
: 過了兩天都沒什麼人回應 我再把題目說清礎些
: 或者先簡化一下題目 當沙漠長只有400km
: 採用如下兩種方法 (為了敘述方邊 1L的油當作跑1KM)
今天想想 把折反點 分的越細 就能運越多...
還沒仔細去算極限是多少...
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.112.249.83
> -------------------------------------------------------------------------- <
作者: weijr (173/124) 看板: puzzle
標題: Re: 【益智問題】[計算]後勤問題
時間: Tue Sep 17 03:50:04 2002
※ 引述《arist ( 川 )》之銘言：
: ※ 引述《arist ( 川 )》之銘言：
: : 第一行中 有著寫 可跑200km ?
: : 這可比九連環 要複雜的多 不是多在次數 而是難在 折反點
: : 想問的是 如何才耗能最少油 折返點的決定處 要是如何....
: : 過了兩天都沒什麼人回應 我再把題目說清礎些
這題有點複雜，如果有漂亮的解，也要花一點時間才找得到。
: : 或者先簡化一下題目 當沙漠長只有400km
: : 採用如下兩種方法 (為了敘述方邊 1L的油當作跑1KM)
: 今天想想 把折反點 分的越細 就能運越多...
對長途來說，分細一點似乎不錯，但要仔細計算。
我沒有算最小值，微分要拿筆算了。
短程來說，還要扯到整數運算，要仔細看一下才知道。
用遞回方式應該是最直接的。距離n需要多少油，n+d就只要把那麼多的油運到
d就行了。（包含最後一趟的200-d）
但這只是給出一組解而已。
: 還沒仔細去算極限是多少...
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 131.215.252.211