表明贪婪算法表现出最优子结构和贪婪选择
我需要帮助证明算法具有贪婪选择属性和最优子结构。
问题背景：
考虑一个问题，其中一家公司拥有 n 个通过高速公路连接的加油站。 每个加油站的气罐供应量有限。g_i。由于该公司不知道哪个加油站访问量最大，因此他们希望所有加油站的加油量相同。
因此，他们租了一辆加油卡车，用卡车在加油站之间运输天然气。然而，卡车每行驶一公里也消耗 1 个油罐。
你的任务是帮助连锁店计算最大的气罐数量g_bar 他们可以在所有车站购买。
考虑这个例子：这里我们有 g = (20, 40, 80, 10, 20) 和 p = (0, 5, 13, 33, 36)（以公里为单位）。为了将一罐煤气罐从 3 号站发送到 加油站 4 我们需要在卡车上放置 41 个油罐，因为加油车在到达目的地之前会消耗 40 个油罐（要发送两个油罐，我们需要在卡车上放置 42 个油罐）。 该示例的最佳 g_bar 为 21，可通过以下方式实现：
站点 2 向站点 1 发送 11 个煤气罐。一个煤气罐到达，但途中消耗了 10 个。< /p>
3 号站向 4 号站发送 59 个气罐。其中 19 个到达，40 个在途中消耗。
4 号站现在有 29 个气罐，并向 5 号站发送 8 个。其中两个到达 六个在途中被消耗掉。
气罐的最终分布为：(21,29,21,21,22)。
给定一个整数g_bar。确定是否可以在每个加油站获得至少 g_bar 个汽油罐。
为了使贪婪选择属性和最优子结构对决策问题有意义，您可以将最优解决方案定义为每个加油站至少具有 g_bar 个加油罐的解决方案，如果这样的解决方案是存在的；否则，任何解都是最优解。
输入：位置p_i和gas-can供应g_i每个柱。这里，g_i 是位置 p_i 处的柱的供给。您可以假设位置已排序 - 即 p_1 p_1 p_1 p_1 p_1 p_1 p_1 p_2 < 。 。 。 < p_n。
输出：最大量g_bar，使得卡车转移后每个加油站至少能有g_bar的气罐供应车站之间的气罐。
我如何证明贪婪选择和最优子结构？
I am in need of help proving that an algorithm has greedy choice property and optimal substructure.
Context of the problem:
Consider a problem where a company owns n gas stations that are connected by a highway.
Each gas station has a limited supply g_i of gas-cans. Since the company don't know which gas station is most visited they want all of them to have the same amount of gas.
So they hire a fueling-truck to haul gas between the stations in their truck. However, truck also consumes 1 gas-can per kilometer driven.
Your task will be to help the chain calculate the largest amount of gas-cans g_bar
they can have at all Stations.
Consider the example: Here we have g = (20, 40, 80, 10, 20) and
p = (0, 5, 13, 33, 36) (in kilometers). In order to send one gas-can from station 3 to
station 4 we need to put 41 gas-cans in the truck, as the fueling-truck will consume 40 before reaching their destination (to send two gas-cans we need to put 42 in the truck).
The optimal g_bar for the example is 21 and can be achieved as follows:
Station 2 sends 11 gas-cans towards Station 1. One gas-can arrives while ten are consumed on the way.
Station 3 sends 59 gas-cans towards Station 4. 19 arrive while 40 are consumed on the way.
Station 4 now has 29 gas-cans and send eight towards Station 5. Two of these arrive
and six are consumed on the way.The final distribution of gas-cans is: (21, 29, 21, 21, 22).
Given an integer g_bar. Determine whether it is possible to get at least g_bar gas-cans in every Gas Station.
in order for the greedy choice property and optimal substructure to make sense for a decision problem, you can define an optimal solution to be a solution with at least g_bar gas-cans in every gas station if such a solution exists; otherwise, any solution is an optimal solution.
Input: The position p_i and gas-can supply g_i of each bar. Here g_i is the supply for the bar at position p_i. You may assume that the positions are in sorted order – i.e. p_1 < p_2 < . . . < p_n.
Output: The largest amount g_bar, such that each gas-station can have a gas-can supply of at least g_bar after the truck have transferred gas-cans between the stations.
How can i prove Greedy Choice and Optimal Substructure for this?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
让我们定义一个最佳解决方案：每个站点至少有
X个气罐（X=g_bar）。证明贪婪属性
让我们假设我们的解决方案不是最优的。必须存在一个站
i使得gas[i]X。根据我们的算法，我们从i+1站借用了X -gas[i]（这是一个有效的举动，因为我们已经找到了解决方案）。现在i站有gas = X。这与最初的假设相矛盾，即必须存在一个站i使得gas[i]X，这意味着我们的解决方案并不是次优的。因此，我们证明了最优性。证明最优子结构
假设我们有一个大小为
N'的站点子集，并且我们的解决方案不是最优的。同样，如果解决方案不是最优的，则必须存在一个站i使得gas[i]gas[i]i。X。您可以再次使用贪心证明来证明我们的解决方案不是次优的。由于我们对每个任意子集都有最优解，因此我们证明我们有最优子结构。Let's define an optimal solution: Each station has at least
Xgas cans in each station (X=g_bar).Proving greedy property
Let us assume our solution is sub-optimal. There must exist a station
isuch thatgas[i]<X. Based on our algorithm, we borrowX - gas[i]from stationi+1(which is a valid move, since we had already found a solution). Now stationihasgas = X. This contradicts the original assumption that there must exist a stationisuch thatgas[i]<X, which means our solution isn't suboptimal. Hence, we prove the optimality.Proving optimal substructure
Assume we have a subset of the stations of size
N', and our solution is suboptimal. Again, if the solution is suboptimal, there must exist a stationisuch thatgas[i]<X. You can use the greedy proof again to prove that our solution isn't suboptimal. Since we have optimal solution for each arbitrary subset, we prove that we have optimal substructure.