表明贪心算法表现出最优子结构和贪心选择
Showing that Greedy algorithm exhibits optimal substructure and greedy choice
我需要帮助证明算法具有贪心选择 属性 和最优子结构。
问题背景：
考虑一个问题，一家公司拥有 n 个通过高速公路相连的加油站。
每个加油站的气罐供应量有限 g_i。由于公司不知道哪个加油站访问量最大，因此他们希望所有加油站都有相同数量的汽油。
所以他们租了一辆加油车，用卡车在加油站之间运送汽油。然而，卡车每行驶一公里也消耗 1 罐汽油。
你的任务是帮助连锁店计算出最大的汽油罐数量g_bar
他们可以在所有车站。
考虑这个例子：这里我们有 g = (20, 40, 80, 10, 20) 和
p = (0, 5, 13, 33, 36)（以千米为单位）。为了从站 3 发送一个气罐到
station 4 我们需要在卡车上放 41 个气罐，因为加油车在到达目的地之前会消耗 40 个（要发送两个气罐，我们需要在卡车上放 42 个）。
该示例的最佳 g_bar 是 21，可以按如下方式实现：
2号站向1号站发送11个气罐。1个气罐到达，10个在途中被消耗。
3号站向4号站发送59个气罐。19个到达，40个在途中消耗。
4 号站现在有 29 个气罐，将 8 个送往 5 号站。其中两个到达
途中消耗了六个。
气罐最终分布为：(21, 29, 21, 21, 22).
给定一个整数 g_bar。确定是否有可能在每个加油站获得至少 g_bar 个汽油罐。
为了使贪心选择 属性 和最优子结构对决策问题有意义，您可以定义一个最优解，使其至少具有 g_bar如果存在这样的解决方案，每个加油站的气罐；否则，任何解都是最优解。
输入：位置p_i和气罐供应g_i of每个柱。这里 g_i 是位置 p_i 处柱的供应。您可以假设这些位置是按排序顺序排列的——即 p_1 < p_2 < . . . < p_n.
输出：最大量g_bar，这样每个加油站至少可以有g_bar辆卡车后的气罐供应在车站之间转移了煤气罐。
如何证明贪心选择和最优子结构？
让我们定义一个最优解：每个站至少有X个加油站（X = g_bar）。
证明贪心属性
让我们假设我们的解决方案是 sub-optimal。必须存在一个站点 i 使得 gas[i] < X。根据我们的算法，我们从站点 i+1 借用 X - gas[i]（这是一个有效的举动，因为我们已经找到了解决方案）。现在站点 i 有 gas = X。这与最初的假设相矛盾，即必须存在一个站点 i 使得 gas[i] < X，这意味着我们的解决方案并非次优。因此，我们证明了最优性。
证明最优子结构
假设我们有一个大小为 N' 的站点子集，并且我们的解决方案不是最优的。同样，如果解决方案不是最优的，则必须存在一个站点 i，使得 gas[i] < X。您可以再次使用贪心证明来证明我们的解决方案并非次优。由于我们对每个任意子集都有最优解，我们证明我们有最优子结构。
我需要帮助证明算法具有贪心选择 属性 和最优子结构。
问题背景：
考虑一个问题，一家公司拥有 n 个通过高速公路相连的加油站。
每个加油站的气罐供应量有限 g_i。由于公司不知道哪个加油站访问量最大，因此他们希望所有加油站都有相同数量的汽油。
所以他们租了一辆加油车，用卡车在加油站之间运送汽油。然而，卡车每行驶一公里也消耗 1 罐汽油。
你的任务是帮助连锁店计算出最大的汽油罐数量g_bar
他们可以在所有车站。
考虑这个例子：这里我们有 g = (20, 40, 80, 10, 20) 和
p = (0, 5, 13, 33, 36)（以千米为单位）。为了从站 3 发送一个气罐到
station 4 我们需要在卡车上放 41 个气罐，因为加油车在到达目的地之前会消耗 40 个（要发送两个气罐，我们需要在卡车上放 42 个）。
该示例的最佳 g_bar 是 21，可以按如下方式实现：
2号站向1号站发送11个气罐。1个气罐到达，10个在途中被消耗。
3号站向4号站发送59个气罐。19个到达，40个在途中消耗。
4 号站现在有 29 个气罐，将 8 个送往 5 号站。其中两个到达 途中消耗了六个。
气罐最终分布为：(21, 29, 21, 21, 22).
给定一个整数 g_bar。确定是否有可能在每个加油站获得至少 g_bar 个汽油罐。
为了使贪心选择 属性 和最优子结构对决策问题有意义，您可以定义一个最优解，使其至少具有 g_bar如果存在这样的解决方案，每个加油站的气罐；否则，任何解都是最优解。
输入：位置p_i和气罐供应g_i of每个柱。这里 g_i 是位置 p_i 处柱的供应。您可以假设这些位置是按排序顺序排列的——即 p_1 < p_2 < . . . < p_n.
输出：最大量g_bar，这样每个加油站至少可以有g_bar辆卡车后的气罐供应在车站之间转移了煤气罐。
如何证明贪心选择和最优子结构？
让我们定义一个最优解：每个站至少有X个加油站（X = g_bar）。
证明贪心属性
让我们假设我们的解决方案是 sub-optimal。必须存在一个站点 i 使得 gas[i] < X。根据我们的算法，我们从站点 i+1 借用 X - gas[i]（这是一个有效的举动，因为我们已经找到了解决方案）。现在站点 i 有 gas = X。这与最初的假设相矛盾，即必须存在一个站点 i 使得 gas[i] < X，这意味着我们的解决方案并非次优。因此，我们证明了最优性。
证明最优子结构
假设我们有一个大小为 N' 的站点子集，并且我们的解决方案不是最优的。同样，如果解决方案不是最优的，则必须存在一个站点 i，使得 gas[i] < X。您可以再次使用贪心证明来证明我们的解决方案并非次优。由于我们对每个任意子集都有最优解，我们证明我们有最优子结构。