algorithm - 旅行推销员 - 城市预算

Question

一家冰淇淋工厂在世界上拥有 n 个分支机构 S1,S2,...Sn。销售人员必须经过每个分支机构才能挑选不同的产品。

1. 当销售人员完成他在分支机构 1<= j <= n 的工作时，他的预算中有 Mj 钱(最初为 0)
2. 对于从分支 Sj 出发的 j <= n - 1，一架飞机离开到下一个分支 Sj+1，这将花费 Cj 钱。

一架飞机从最后一个分支 Sn 起飞到第一个分支 S1，花费 Cn 钱。

我们知道累积的钱数 Mj(从 j = 1 到 n 的西格玛)等于他花费的钱数 Cj(从 j = 1 到 n 的西格玛)。销售人员必须用他从分支机构收到的钱来支付飞机费用。公司让销售人员免费决定他从哪里开始他的旅程(他将在那里结束他的旅程)。

我如何证明总有 1 <= j <= n 以便如果销售人员从 Sj 开始他的旅程，他可以用他的预算完成他的旅程？

我考虑过鸽笼原则，但无法真正将我的想法形式化。任何其他建议也很好!

Answer 1

想想如果我们允许金额变为负值并且他不断循环多次，他在每个城市将有多少钱。

钱将遵循某种周期模式，周期为 n。

如果我们从他钱最少的城市开始，那么模式将始终保持非负，这样他就有足够的钱完成这条路线。

补充说明

定义 S(k) 为 Mi-Ci 中 i 取值范围为 0 到 k 的和。S(k) 表示销售员从城市 0 旅行到 k 并购买下一张机票后将拥有的金额。

我们知道S(n)等于0。

令 m 为使 S(x) 最小化的 x 值。

然后从城市 m 到城市 i 的旅行将花费 S(i)-S(m)，通过构造它总是大于或等于零。