爲了儘量減少時間，女人應該把貓帶回來？

Question

一個女人看着她的貓在不同的方向以不同的速度一個接一個離開。她帶着一個額外的座位摩托車，跟隨着貓，一次拿起一隻貓，並把它們帶回家。每隻貓以恆定的個人速度Vi移動並在時間Ti離開家。爲了儘量減少時間，女人應該把貓帶回來？

我想解決這個問題，但不知道如何開始。

Answer 1

摘要：

排序貓根據度量V/X降序排列，其中v是貓的恆定速度，x是貓的在時間t = 0的沒有按初始位移不管你如何打破關係。一旦訂單初步建立起來，只要遵循它，它仍然是獲得貓的最有效的順序;所以按照它。

考生揭穿：

在這兩種情況下，允許摩托車速度爲w = 20

1. 所以建議你的貓，以從最快到最慢。反例：Cat＃1（x，v）=（1,9）和Cat＃2（x，v）=（100,10）。

2. 建議您從最接近到最遠的順序獲得貓。反例：Cat＃1（x，v）=（1,1）和Cat＃2（x，v）=（2，100）。

詳細推導：

設C（K）是指第k個貓小姐拿起，V（k）的指的是貓和x（k）的速度，以貓的初始位移（在時間t = 0時，我們設定了女士最初爲追求第一隻貓而啓動她的摩托車的時間）。

採取率先拿到貓的總時間爲：

t(1) = 2 * x(1)/(w - v(1)) 

其中w是摩托車的恆定速度。由於這種表達將是重要的，我們可以激勵它的每一個部分：

1. 2 *來自於一個事實，那位女士必須抓住貓，然後花費大量的時間返回家貓相同數量;
2. x(1)/(w - v(1))是要達到的貓，也就是所花費的時間，通過旅行比貓的v(1)w - v(1)快近的距離x(1)。

拿到第一兩隻貓的時間是：

t(2) = t(1) + 2 * (x(2) + v(2)t(1))/(w - v(2)) 

也就是說，它需要的時間等於時間拿到第一貓加上獲得第二個貓的時間。額外的v(2)t(1)術語解釋了第二隻貓在女士獲得第一隻貓時移動的事實;否則，這部分是一樣的。

重新整理這個表達式中，我們得到：

t(2) = t(1)(1 + 2 * v(2)/(w - v(2))) + 2 * x(2)/(w - v(2)) 

我們定義了以下微分項：

T(k) = 2 * x(k)/(w - v(k)) 
s(k) = 2 * v(k)/(w - v(k)) + 1 

現在我們改寫：

t(1) = T(1) 
t(2) = s(2)T(1) + T(2) 

，並繼續

t(1) = T(1) 
t(2) = s(2)T(1) + T(2) 
t(3) = s(3)s(2)t(1) + s(3)T(2) + T(3) 
... 
t(n) = s(n)...s(2)T(1) + s(n)...s(3)T(2) + ... + T(n) 

這最後的表達使我們的總時間來獲取所有n貓：

s(n)...s(2)T(1) + s(n)...s(3)T(2) + ... + T(n) 

現在我們假設我們在這貓是最有效的順序可能拿起一個最佳的解決方案。爲了推導出這個假設的最優解的有用性質，我們可以使用假設的最優性來推斷交換貓產生的解決方案並不是最好的。試想一下，交換貓j和j+1：涉及T(k)爲k < j

... + s(n)...s(j+1)T(j) + s(n)...s(j+2)T(j+1) + ... 
<= ... + s(n)...s(j)T(j+1) + s(n)...s(j+2)T(j) + ... 

條款兼得s(j)和s(j+1)和乘法交換律，他們是通過交換的影響。涉及T(k)的條款k > j + 1既沒有s(j)也沒有s(j+1)，因此不能受交換的影響。只有T(k)這樣j <= k <= j + 1被交換的影響，所以我們可以刪除同類項條款：

s(n)...s(j+2)s(j+1)T(j) + s(n)...s(j+2)T(j+1) 
<= s(n)...s(j+2)s(j)T(j+1) + s(n)...s(j+2)T(j) 

部分積s(n)...s(j+2)是共同的所有其他條款，並且必須是積極的，所以我們可以刪除此類似的條款通過將不等式的兩邊：

s(j+1)T(j) + T(j+1) <= s(j)T(j+1) + T(j) 

重新排列這如下：

(s(j+1) - 1)T(j) <= (s(j) - 1)T(j+1) 

翅盟友：

(s(j+1) - 1)/T(j+1) <= (s(j) - 1)/T(j) 

回顧我們的s(k)和T(k)定義，簡化了把這種在v和x方面：

v(j+1)/x(j+1) <= v(j)/x(j) 

那就是：如果我們有一個最佳的解決方案，它一定是這樣的貓的速度與初始位移之比必須按降序排列。這是一個必要但可能不充分的條件。

注意，這個結果與直覺一致：

• 仍然獲得最後的貓（V = 0）
• 拿到沒有離開但第一貓（X = 0）
• 獲取貓接近摩托車的速度第一（或從不）
• 獲取貓是真正遠離最後的（X - > + INF）

它還給出正確的結果FO兩貓案;在這種情況下，如果速度與位移的比率相等，那麼可以很容易地表明，你得到貓的順序是無關緊要的（如果它們不相等，你必須先得到較高比例的貓）。

現在 - 我還沒有解決的情況下，貓可能有相同的比例。這對我來說並不是顯而易見的，你以相同的比例獲得貓的順序並不重要。

但是，假設您選擇了最佳方式直到某個點k < n。現在你需要決定兩隻貓有着相同的比例。正如我們已經提到的那樣，對於兩貓問題，這是一種洗滌：所以我認爲答案是，你選擇哪一個並不重要，因爲兩者中的任何一個的順序都會花費相同的時間並且「看起來」相同之後。要看到，在相同的比例開始兩隻貓保持相同的比例：

v(i)/x(i) = c; X(i) = x(i) + v(i)t = x(i) + x(i)ct = x(i)(1 + ct) 
v(j)/x(j) = c; X(j) = x(j) + v(j)t = x(j) + x(j)ct = x(j)(1 + ct) 

所以比隨時間的變化（如果你把X作爲新的初始位移），但有兩個具有相同比值開出貓將保留它。新的比例將是：

v/x = c; v/X = v/x(1 + ct) = c/(1 + ct) 

重要的是要注意，這些比率也不互相「交叉」;如果你有較高或較低的比例開始時，它會隨着時間而改變，但不會變得比其他貓的比率較高或較低的：基於所有這些考慮

c(i)/(1 + c(i)t) > c(j)/(1 + c(j)t) 
<=> c(i) + c(i)c(j)t > c(j) + c(i)c(j)t 
<=> c(i) > c(j) 

，我最好的答案是：

按照度量值v/x降序對貓進行排序。你如何打破關係並不重要。按照該順序獲取貓。

Answer 2

更新

感謝@ Patrick87反例，我知道我的解決方案並不在一般情況下工作，但是，我要去，因爲它提供了額外的假設下，一個簡單的解決方案，離開這裏是所有貓在時間0開始從家中搬家。請參閱@ Patrick87解決方案以獲取一般解決方案。

答案很簡單：

她必須以最快的貓開始。即按velocity訂購的貓（按降序排列）。

簡化問題：假設只有兩隻貓，一隻正在運行另一隻非常緩慢地行走。首先你會去哪一個？

詳細的解答：

從家裏所有的貓的總距離在0時0：

X(0) = 0 

因此，如果我們假設女人抓住最後貓時間Tn那麼女人已經在Tn旅行的總距離是：

X(Tn) = (V1 * T1) + ... + (Vn * Tn) 

其中Ti是她抓到n的貓的時間。 Vi值是預先確定的，所以我們需要根據Ti的值最小化該方程。

我們有n正V值與n積極T係數分配給他們。在這些條件下最小化它很容易：

給最大的V，最小系數T等等。

這意味着從最快的貓（最大的V）開始，並將其返回（乘以最小的T）並繼續。