做出完整的圆形路径，最短路径运动？
我在接受采访时得到了这个问题，但我无法解决。
你有一条环形公路，有N个加油站。 你知道每个车站有多少气体。 你知道从一个站到下一个站所需的气体量。 你的车从0气开始。 问题是：创建一个算法，以了解您必须从哪个加油站开始驾驶以完成圆形路径。 它没有指定您必须访问所有站。 你只能顺时针驾驶。
我不得不在c＃中做到这一点
我开始的唯一代码是GasStation实体
class GasStation int gasAtStation; int gasToMoveToNextStationNeeded; string nameOfGasStation; GasTation wheretoStart(List list) { } 我是这样做的：
static void Main(string[] args) { int[] gasOnStation = {1, 2, 0, 4}; int[] gasDrivingCostTonNextStation = {1, 1,2, 1}; FindStartingPoint(gasOnStation, gasDrivingCostTonNextStation); } static void FindStartingPoint(int[] gasOnStation, int[] gasDrivingCosts) { // Assume gasOnStation.length == gasDrivingCosts.length int n = gasOnStation.Length; int[] gasEndValues = new int[n]; int gasValue = 0; for (int i = 0; i < n; i++) { gasEndValues[i] = gasValue; gasValue += gasOnStation[i]; gasValue -= gasDrivingCosts[i]; } if (gasValue < 0) { Console.WriteLine("Instance does not have a solution"); Console.ReadLine(); } else { // Find the minimum in gasEndValues: int minI = 0; int minEndValue = gasEndValues[0]; for (int i = 1; i < n; i++) { if (gasEndValues[i] < minEndValue) { minI = i; minEndValue = gasEndValues[i]; } } Console.WriteLine("Start at station: " + minI); Console.ReadLine(); } }
谢谢
解决这个问题的一种简单方法是使用powershell方法。 即尝试每一个可能性并抛弃那些不起作用的东西。
即依次从每个加油站开始（下面重复每个起始站）。
- 有一个定义当前气体水平的变量。
- 按顺时针顺序循环通过每个加油站。
- 加油（按加油站数量增加燃气）。
- 检查你可以移动到下一站
(gas >= gasToMoveToNextStationNeeded)- 如果没有，这不是一个解决方案，所以移动到下一个起始位置。
- 如果是这样，减去使用的气体量，然后继续，直到你再次开始。
- 如果你回到起始加油站，你会有答案。
编辑按照@ Vash的回答 ，作为决定从哪里开始的改进，折扣站没有足够的气体到达下一站并按照燃气量（降序）的顺序通过起始站。
请注意，这假设我们访问所有加油站。 如果您需要最佳解决方案，则需要改进跳过加油站（问题没有说明这一点）。
这是@George Duckett答案的优化案例。
- 选择并记住您的起始站。
- 循环（1）顺时针通过站。
- 得到一个燃料。
- 如果你有足够的燃料，去下一站，减少剩余燃油量，继续循环（1）
如果你到达了起始站 – 问题就解决了。
如果在某些车站，你没有足够的燃料来到下一个车站
- 记住你的终点站。
- Distance_to_start = 0，fuel_to_start = 0
- 逆时针从起始站循环（2）。
- 向您的柜台添加可用燃料和到下一站的距离
- 如果fuel_to_start> distance_to_start，你有一些多余的燃料。 将此站标记为您的新开始并再次循环（1） – 可能您现在可以继续。
- 否则，继续循环（2）
如果你逆时针走到已经访问过的车站 – 运气不好，那么车站上没有足够的燃料可以完全循环。
任务真的很开放。 当您进行循环时，最佳选择是从具有最大燃料量的站开始。 这意味着您将能够驾驶汽车并开车到下一个最近的车站。
当我们有一个起点时，我们只需要决定我们需要停哪个加油站。 对于第一次运行，我们可以停止每个站。
编辑。
与Lasse V. Karlsen讨论后出现的小改进。
如果所选的第一站将不能成功进行循环。 然后以较小的*燃油/道路比例以相同的方式选择下一个。
*小于第一个选择的站比例。
制作电台的循环列表。 找到具有正值的任何电台
超额=（gasAtStation – gasToMoveToNextStation需要）
这是目前的基础。
当下一站具有负超额值时，将其gasAtStation和gasToMoveToNextStationNeeded添加到当前基本字段，并从列表中删除此站。
循环重复所有正站。
当没有更多的站点删除：
如果一个或一些非负站仍在列表中 – 其中任何一个都适合作为起点。
例：
A（-50）B（100）C（-20）D（-90）E（60）[C-> B]
A（-50）B（80）D（-90）E（60）[D-> B]
A（-50）B（-10）E（60）[A-> E]
B（-10）E（10）[B-> E]
E（0）
虽然尝试每个起始站当然工作正常，但它需要二次时间，而有一个简单的线性时间算法。
如果燃油油位变为负值，请使用可以继续行驶的魔车。 从任意车站出发，进行全程旅行，参观每个车站。 如果燃油量低于零，则无法解决问题。 否则，启动的最佳站点是到达时的燃料水平最低的站点。
这是有效的，因为除了恒定的偏移之外，所有可能的游览的燃料水平是相同的。
如果我们定义从A站到B的行程包括GasAtStation A和TripCost。 然后，对于每次旅行，我们都有TripBalance = GasAtStation-TripCost
所有行程余额的总和必须大于或等于零，否则不存在解决方案。 解决方案包括一个列表，其中包含每个加油站的行程余额，并迭代保留tripBalance变量的项目，如果tripBalance变为负值，则行程应从下一个加油站开始，如果是，我们重置tripBalance我们继续处理，直到我们检查列表中的最后一个条目：
public int FindFirstStation(List tripBalances) { if (tripBalances.Sum() < 0) return -1; var firstStation = 0; var tripBalance = 0; for (int i = 0; i < tripBalances.Count; i++) { tripBalance += tripBalances[i]; if (tripBalance < 0) { tripBalance = 0; firstStation = i + 1; // next station } } return firstStation; }
我使用以下代码测试它：
[TestMethod] public void Example() { var tripBalances = new List { 0, 1, -2, 3 }; var resolver = new GasStationResolver(); var indexOfGasStation = resolver.FindFirstStation(tripBalances); Assert.AreEqual(3, indexOfGasStation); }
看到传递的值是从问题标题中给出的示例中得出的值。 在这种情况下，答案是我们列表中的最后一个加油站应该是第一个加油站。 最后，如果没有解决方案，则该方法返回-1。
另一个例子涵盖了天然气含量较高的站点不是解决方案：
/// /// Station 1 - Gas: 3 Cost: 4 /// Station 2 - Gas: 10 Cost: 11 /// Station 3 - Gas: 8 Cost: 9 /// Station 4 - Gas: 6 Cost: 3 /// Station 5 - Gas: 4 Cost: 2 /// /// Then - Trip Balances are: /// Station 1 - -1 /// Station 2 - -1 /// Station 3 - -1 /// Station 4 - 3 /// Station 5 - 2 /// [TestMethod] public void SecondExample() { var tripBalances = new List { -1, -1, -1, 3, 2 }; var resolver = new GasStationResolver(); var indexOfGasStation = resolver.FindFirstStation(tripBalances); Assert.AreEqual(3, indexOfGasStation); }
找到气体最多的加油站，但是当加入油箱时下一站的气体不超过油箱的容量。
这或许呢？
- 找到含有最多气体的加油站
- 列出所有加油站，并取其燃油值，减去那里的行驶费用
- 开车到最高价值的加油站
- 重复，直到访问所有加油站