吉普问题

https://en.wikipedia.org/wiki/Jeep_problem

https://zhuanlan.zhihu.com/p/7236950040

某吉普位于原点，在原点处有 \(n\) 单位燃油。吉普的油箱中最多可存储 \(m\) 单位燃油。吉普可以随时随地将任意单位燃油卸载于当地，或从当地载入油箱。吉普每单位时间可移动一单位长度，且移动时每单位时间必须消耗油箱中的一单位燃油。

1. 求吉普能够移动的最大位移。
2. 现吉普需要将燃油尽可能多地搬运到位移 \(l\) 处，求此处的燃油数的最大值。
3. 若 \(n = +\infty\)，现吉普需要到达位移 \(l\) 处，求总过程的最小油耗。
4. 现吉普可以随时随地出售其油箱中存储的任意单位的燃油，在位移 \(l\) 处的出售价格固定为每单位燃油 \(l\) 单位收益。吉普需要规划出售策略，并使其最终能够返回原点，求总过程可获得的收益的最大值。

推广：

• 燃油消耗效率与载重量有关
• 仅允许在给定的位置卸载/载入燃油
• 仅允许在给定的次数内卸载/载入燃油
• 非匀速吉普

本文不讨论这些复杂的推广。

解答

引理

记一个满油箱为 \(m\) 单位的燃油，起始时有 \(k\) 单位的满油箱。

搬运是分批的，每一批的燃油最多存储一个满油箱，不足一个满油箱的非空燃油仍需算作一批。

每阶段搬运，从位移 \(s_i\) 处将 \(n_i\) 批燃油全部搬运到 \(s_{i+1} > s_i\) 处，记 \(\Delta s_i = s_{i+1} - s_i\)。那么，搬运将涉及奇数次趟，其中去程趟从 \(s_i\) 满载油箱到达 \(s_{i+1}\)，返程趟从 \(s_{i+1}\) 载油 \(\Delta s_i\) 回到 \(s_i\)，且最后一趟是去程。

因此，将 \(n_i\) 批燃油推进 \(\Delta s_i\) 距离，将往返 \(2 n_i - 1\) 趟。

1：给定燃油的最大位移

https://mathworld.wolfram.com/JeepProblem.html

记 \(n = km + t\)，\(t \in [0, m), k \in \mathbb{N}\)。

一种贪心策略的思想是“尽量满载”，它分两个阶段，描述如下：

1. 不足满油箱的运输。我们需要在消耗恰好 \(t\) 单位的燃油下，将 \(k+1\) 批燃油从原点全部搬运到某个 \(s_k > 0\) 处。

由引理，这将往返 \(2 k + 1\) 趟，位移满足

\[ s_k = \frac{t}{2 k + 1}. \]

2. 满油箱运输。将不足的油消耗完后，剩余 \(k\) 个满油箱，随后共有 \(k\) 个阶段的搬运。对每个倒数的 \(i \in \{k, k - 1, \dots, 1\}\)：

第 \(i\) 阶段，从位移 \(s_i\) 处将 \(i\) 单位的满油箱全部搬运到 \(s_{i-1} > s_i\) 处。并且恰好消耗 \(1\) 单位满油箱，即 \(m\) 单位的燃油。阶段结束时，在 \(s_{i+1}\) 处共有 \(i - 1\) 单位的满油箱。

由引理，这将往返 \(2 i - 1\) 趟，因此每阶段的位移满足

\[ \Delta s_i = \frac{m}{2 i - 1}. \]

故这将贡献位移

\[ \frac{m}{2k - 1} + \dots + \frac{m}{2 \cdot 1 - 1} = \sum_{i=1}^k \frac{m}{2 i - 1}. \]

综上所述，该策略下的总位移为

\[ d = \frac{t}{2 k + 1} + \sum_{i=1}^k \frac{m}{2 i - 1}. \]

这个解颇有调和级数的味道。可以证明，奇数项调和级数的前 \(k\) 项和 \(\sum_{i=1}^k \frac{1}{2 i - 1} = \Theta(\log k)\)。

可以证明，这就是使得位移最大化的策略，但不会证。

计算 \(d\) 的时间复杂度一般是 \(O(k) = O(n/m)\)。

例子

设 \(n=2, m=1\)，那么 \(k = 2, t = 0\)，没有不足满油箱的运输，满油箱运输需要进行 \(2\) 个阶段的搬运。

第 \(i=2\) 阶段，从 \(0\) 将 \(2\) 个满油箱搬运到 \(\frac{1}{3}\) 处，共 \(3\) 趟。

第 \(i=1\) 阶段，从 \(\frac{1}{3}\) 将 \(1\) 个满油箱搬运到 \(\frac{4}{3}\) 处，共 \(1\) 趟，其实就是满载油全速前进。

总位移为 \(4/3\)。

2：给定位移的最大移动燃油

https://math.stackexchange.com/questions/1604871/jeep-problem-variant-cross-the-desert-with-as-much-fuel-as-possible

记 \(n = km + t\)，\(t \in [0, m), k \in \mathbb{N}\)。为简便起见，本小题我们仅考虑 \(t=0\) 的情况，\(t > 0\) 的仅需进行一次不足满油箱的运输即可。

设 \(f(x)\) 表示吉普从原点将 \(n\) 单位燃油搬运到位移 \(x\) 处，最终在 \(x\) 处的最大燃油数，那么答案在 \(f(l)\)。

从 \(0\) 到 \(x\) 处搬运 \(k\) 个满油箱，将往返 \(2 k - 1\) 趟。我们分段考虑：

• 当 \(x \leq \frac{m}{2 k - 1}\) 时，直接做 1 阶段的搬运显然是最优策略。吉普将往返于 \(0\) 和 \(x\) 之间 \(2 k - 1\) 趟，每趟的去程尽量满载，返程只需载入 \(x\) 单位燃油。因此，\(\forall x \in [0, \frac{m}{2 k - 1}]\)，有

  \[ f(x) = n - (2k - 1) x. \]

• 记 \(x_1 = \frac{m}{2 k - 1}\)。当 \(x \in (x_1, x_1 + \frac{m}{2(k-1) - 1}]\) 时，需要做一阶段的搬运到 \(x_1\) 处，然后再做一阶段的搬运到 \(x\) 处。吉普将往返于 \(x_1\) 和 \(x\) 之间 \(2 (k-1) - 1\) 趟，每趟的去程尽量满载，返程只需载入 \(x - x_1\) 单位燃油。因此，\(\forall x \in (x_1, x_1 + \frac{m}{2(k-1) - 1}]\)，有

  \[ f(x) = (n - m) - (2 (k-1) - 1) (x - x_1). \]

• 记 \(x_2 = x_1 + \frac{m}{2 (k-1) - 1}\)。当 \(x \in (x_2, x_2 + \frac{m}{2(k-2) - 1}]\) 时，同理有

  \[ f(x) = (n - 2m) - (2 (k-2) - 1) (x-x_2). \]

• 以此类推，记 \(x_i = x_{i-1} + \frac{m}{2(k-(i-1)) - 1}\)，在第 \(i\) 个搬运区间，即 \(x \in (x_i, x_i + \frac{m}{2(k-i) - 1}]\) 时，有

  \[ f(x) = (n - im) - (2 (k-i) - 1) (x-x_i). \]

• 直到 \(i = k\) 时，无法继续搬运。即 \(f(x)\) 的支撑集为 \([0, \sum_{i=1}^k \frac{m}{2 i - 1})\)。\(f(x)\) 在其支撑集上是分段线性函数，每个分段区间的长度越来越长，斜率的绝对值越来越小，很有意思。

求解时，我们只需计算 \(l\) 落在哪个搬运区间内，然后计算 \(f(l)\) 的值即可。时间复杂度 \(O(k) = O(n/m)\)。

例子

猴子背香蕉问题 一个猴子身带 100 个香蕉，他距离家 50 米。这个猴子要带香蕉回去，但是他一次最多只能背 50 个香蕉，而且，每走一米他就要吃掉一个香蕉（往回走也要吃香蕉）。这个猴子最后最多可以带多少个香蕉到家？

解答 \(n=100, m=50, l=50\)，故 \(k=2, t=0\)，故搬运区间端点为 \(x_1 = \frac{50}{3}, x_2 = \frac{50}{3} + 50\)。

猴子首先做一阶段搬运，将香蕉搬到 \(x_1\) 处，此时剩余 \(n-m=50\) 个香蕉。然后再做一阶段搬运，搬到 \(l\) 处，剩余香蕉数为

\[ f(l) = (n-m) - (2(k-1) - 1)(x - x_1) = 50 - \left(50 - \frac{50}{3} \right) = \frac{50}{3}. \]

因此这个猴子最后最多可以带 \(\frac{50}{3}\) 个香蕉到家。

3：给定距离的最小耗油

https://blog.nowcoder.net/n/83802b6ba20e4137ba87f6d08a9ab9e4

为了让吉普以最小的油耗通过，需要在区间 \([0, l)\) 中建立若干个临时加油站，且贪心地，每个加油站的油都恰好被使用完毕。进一步地，除起点加油站外，每个加油站的油量都是 \(km\)，其中 \(k \in \mathbb{N}^*\)。

我们考虑倒推：在最后一个加油站中，吉普车加满油后全速前进就到达了目的地。同理，在倒数第二个加油站中，吉普车需来回倒腾，直到其到达最后一个加油站时，该加油站的油恰好够其加满。

进一步贪心地，我们发现，吉普车倒推设置加油站的过程，就是一系列阶段的搬运，除了从起点到首个加油站的搬运之外，每阶段的搬运恰好消耗一单位的满油箱，即 \(m\) 油量。

设最后一个加油站为 \(1\) 号加油站，并且设起点位置为 \(l\)，终点位置为 \(0\)，依次编号：

• \(1\) 号加油站的位置为 \(x_1 = m\)，油量为 \(m\)
• \(2\) 号加油站的位置为 \(x_2\)，油量为 \(2 m\)。从该加油站搬运 \(2\) 个满油箱到 \(1\) 号加油站，需要往返 \(3\) 趟，故 \[ x_2 = x_1 - \frac{m}{3} \]
• 以此类推，\(i\) 号加油站的位置为 \(x_i\)，油量为 \(im\)。从该加油站搬运 \(i\) 个满油箱到 \(i-1\) 号加油站，需要往返 \(2 i - 1\) 趟，故 \[ x_i = x_{i-1} - \frac{m}{2 i - 1} \]
• 起点加油站的位置为 \(l\)，其能在经过一阶段搬运后，在 \(k\) 号加油站 \(x_k = \sum_{i=1}^k \frac{m}{2 i - 1}\) 处恰好获得 \(km\) 油量，其中 \(k\) 是使得 \(l - \sum_{i=1}^k \frac{m}{2 i - 1} \geq 0\) 的最大的正整数。

因此，吉普的策略可描述如下：

1. 初次运输阶段，从起点 \(l\) 搬运若干油到 \(k\) 号加油站，位置在 \(\sum_{i=1}^k \frac{m}{2 i - 1}\)，其中 \(k\) 是使得 \(l - \sum_{i=1}^k \frac{m}{2 i - 1} \geq 0\) 的最大的正整数。阶段结束时，吉普车位于 \(k\) 号加油站，且此地恰有 \(km\) 油量。这一阶段的总趟数为 \(2 k + 1\)，总距离即总耗油量为 \((2k + 1) \left(l - \sum_{i=1}^k \frac{m}{2 i - 1} \right)\)。
2. \(k\) 次运输阶段，每次运输，从 \(i\) 号加油站将 \(im\) 油搬运到 \(i-1\) 号加油站，恰好消耗 \(m\) 油量。

故总的油量消耗，也是最小的油量消耗为

\[ (2k + 1) \left(l - \sum_{i=1}^k \frac{m}{2 i - 1} \right) + km \]

其中 \(k\) 是使得 \(l - \sum_{i=1}^k \frac{m}{2 i - 1} \geq 0\) 的最大的正整数。

求解的时间复杂度为 \(O (k) = O (\mathrm e^{2(l/m)})\)。

例子

设 \(m = 500, l = 1000\)，计算

\[ l - \sum_{i=1}^k \frac{m}{2 i - 1} \]

注意到，\(k = 7\) 时，上式的值约为 \(22.4\)，\(k=8\) 时，上式的值将小于 \(0\)，故取 \(k=7\)。

计算得到最小油耗为

\[ (2k + 1) \left(l - \sum_{i=1}^k \frac{m}{2 i - 1} \right) + km \approx 15 \times 22.4 + 7 \times 500 = 3836.5 \]

4：旅行商人

https://blog.csdn.net/fhqfjevfhp/article/details/115543229

https://www.bilibili.com/video/BV1p84y1c7DK/

记 \(n = km + t\)，\(t \in [0, m), k \in \mathbb{N}\)。为简便起见，本小题我们仅考虑 \(t=0\) 的情况，\(t > 0\) 的仅需进行一次不足满油箱的运输即可。

在本小题中，吉普前进的基本策略仍遵循“给定燃油的最大位移”，在途中设置若干个中转点，但其将在途中的某个/某些地方出售燃油，换取最大收益。

贪心地，当吉普设置了最远的一个中转点后，将返回原点，途中每经过一个中转点，都将获取该中转点中保存的所有燃油，然后开回下一个距离原点更近的中转点，直到回到原点为止。每个中转点保存的燃油数恰好能让吉普开回下一个距离原点更近的中转点。

由于我们考虑了最后的返程，因此，将 \(n_i\) 批燃油推进 \(\Delta s_i\) 距离，将往返 \(2 n_i\) 趟。

暂时先不考虑如何出售燃油，我们的策略将包含若干阶段：

• 第一阶段，将 \(k\) 单位的满油箱推进到第一个中转点 \(x_1\)。结束时，该中转点保存 \(k-1\) 单位的满油箱，其位置 \[ x_1 = \frac{m}{2k}. \]
• 第二阶段，将 \(k - 1\) 单位的满油箱推进到第二个中转点 \(x_2\)，满足 \[ x_2 = x_1 + \frac{m}{2(k-1)}. \]
• 以此类推，直到满油箱数目为 \(0\)，到达最后一个中转点 \(x_{k}\)。

接下来我们考虑出售燃油的位置。不妨设在最优策略中，每个搬运区间 \((x_{i-1}, x_{i}]\) 都对应唯一的一个出售位置 \(y_i\)（不会证，猜的），并且，我们一旦决定了这个出售位置，就设置相应搬运阶段的中转点从 \(x_{i}\) 变为 \(y_1 + \dots + y_i\)。在该出售位置，可供出售的燃油是那些“因为提前了中转点而可以在该阶段搬运完后出售的额外燃油”。出售完成，并留下返程所需的 \(y_i - y_{i-1}\) 后，此时剩余的恰好仍是若干个满油箱，我们将它们搬运下一个出售中转点 \(y_{i+1}\) 出售并留下返程所需，以此类推。注意：

• 若 \(y_i - y_{i-1} = x_i - x_{i-1}\)，则该搬运区间实际上不出售任何燃油，相当于完整的跨大步走了一个搬运阶段。

那么，我们枚举每个出售位置 \(y_1, \dots, y_k\)：

• 对第一个出售位置 \(y_1 \in (0, \frac{m}{2k}]\)，出售的燃油数为 \(m - 2ky_1\)，收益为 \[ r_1 = (m - 2k y_1) y_1 \]
• 对第二个出售位置 \(y_2 \in (0, \frac{m}{2(k-1)}]\)，收益为 \[ r_2 = (m - 2 (k-1) y_1) (y_1 + y_2) \]
• 以此类推，对第 \(i\) 个出售位置 \(y_i \in (0, \frac{m}{2(k-i)}]\)，收益为 \[ r_i = (m - 2 (k-i) y_i) \left(\sum_{j=1}^i y_j \right) \]

故总收益为

\[ R(y_1, \dots, y_k) = \sum_{i=1}^{k-1} r_i = \sum_{i=1}^{k-1} \left((m - 2 (k-i) y_i) \left(\sum_{j=1}^i y_j \right) \right) \]

约束条件为

\[ \forall i, y_i \in \left(0, \frac{m}{2(k-i)} \right]. \]

这是一个关于 \(y_i\) 的多元函数，我们需要求其最大值。这看起来是一个二次优化问题，并没有什么好的方法……

例子

设 \(n=240, m = 60\)，那么 \(k=4, t=0\)。

中转点的位置为 \(x_1 = \frac{15}{2}, x_2 = x_1 + 10, x_3 = x_2 + 15, x_4 = x_3 + 30\)。

于是，总收益函数为

\[ (60 - 8 y_1) y_1 + (60 - 6 y_2) (y_1 + y_2) + (60 - 4 y_3) (y_1 + y_2 + y_3) + (60 - 2 y_4) (y_1 + y_2 + y_3 + y_4). \]

约束条件为

\[ y_1 \leq \frac{15}{2}, y_2 \leq 10, y_3 \leq 15, y_4 \leq 30. \]

我们直接暴力求偏导，求极值点，令四个偏导数为零得到一个线性方程组，解之得到 \(y_1 > \frac{15}{2}\)，不满足约束。

我们令 \(y_1 = \frac{15}{2}\)，然后重新令三个偏导数为零，解之得到一个全部满足约束的组合

\[ y_2 = \frac{585}{68}, y_3 = \frac{405}{68}, y_4 = \frac{135}{34}. \]

代回原收益函数，得到总收益为

\[ \frac{311175}{136} \approx 2288.05. \]