证明贪心算法的正确性（Chatgpt辅助完成）
一、最大不相交区间数量问题
问题描述：给定n个区间，选择尽可能多的区间，使得这些区间两两不相交。 贪心算法的思路：按照右端点从小到大的顺序，依次选择右端点最小的区间，并且与前面选择的区间不重叠的区间。
证明：
- 贪心选择性质成立 假设选择的区间为I1、I2、I3……Im，按照右端点从小到大的顺序依次选择，其中Im是右端点最小的区间。对于任意一个区间Ix (1≤x≤m-1)，如果Ix与Im相交，那么Ix的右端点一定大于Im的右端点，否则Ix就会被选择而不是Im。因此，我们可以将Ix替换成Im，得到一个不劣解。因此，贪心选择性质成立。
- 最优子结构性质成立 假设S是最优解，其中选择的区间为I1、I2、I3……Im。假设其中一个区间Ij（1≤j≤m）与后面的某个区间Ik（j
二、背包问题
问题描述：有一个容量为C的背包和n个物品，第i个物品的重量为wi，价值为vi，选择一些物品放入背包，使得背包中物品的总价值最大，求最大总价值。 贪心算法的思路：按照单位重量价值从大到小的顺序，依次选择单位重量价值最大的物品，直到背包装满或者没有物品可选为止。
证明：
- 贪心选择性质成立 假设选择的物品为I1、I2、I3……Im，按照单位重量价值从大到小的顺序依次选择，其中Im是单位重量价值最大的物品。对于任意一个物品Ix (1≤x≤m-1)，如果Ix的单位重量价值大于Im，那么Ix的单位重量价值一定大于Im，否则Ix就会被选择而不是Im。因此，我们可以将Im替换成Ix，得到一个不劣解。因此，贪心选择性质成立。
- 最优子结构性质成立 假设S是最优解，其中选择的物品为I1、I2、I3……Im。假设其中一个物品Ij（1≤j≤m）被替换成了Ii（i>j），那么替换后的总价值为： V' = V + vi*(C - wj) / wi - vj 其中V是替换前的总价值，wj和vj分别是被替换的物品的重量和价值。因为单位重量价值从大到小排序，所以vi/wi > vj/wj，即viwj > vjwi，因此上式可以化简为： V' = V + vi - vj*(wi/wj) 由于vi和vj都是正数，wi/wj也是正数，因此V'
三、最少货币数量支付问题
要用最少货币数支付指定金额，凭直觉我们会得出优先用最大可用面值支付的贪心选择策略。假设A国货币体制为1元、3元、9元、27元，B国货币体制为1元、4元、5元、7元，对这两种货币体制，分别证明最大面值优先支付的策略是否成立。
对于A国货币体制，最大面值优先支付的策略成立。 证明：
- 贪心选择性质成立 假设选择的货币为I1、I2、I3……Im，按照面额从大到小的顺序依次选择，其中Im是面额最大的货币。对于任意一个货币Ix (1≤x≤m-1)，如果Ix的面额大于Im，那么Ix的面额一定大于Im，否则Ix就会被选择而不是Im。因此，我们可以将Im替换成Ix，得到一个不劣解。因此，贪心选择性质成立。
- 最优子结构性质成立 假设S是最优解，其中选择的货币为I1、I2、I3……Im。假设其中一个货币Ij（1≤j≤m）被替换成了Ii（i>j），那么替换后的货币数量为： m' = m - xj + xi 其中xj和xi分别是被替换的货币的数量。因为面额从大到小排序，所以xi > xj，因此m' < m，即替换后得到的解比原来的解更劣。因此，最优子结构性质成立。 因此，对于A国货币体制，最大面值优先支付的策略成立。
对于B国货币体制，最大面值优先支付的策略不成立。
举例说明： 假设需要支付12元，按照最大面值优先支付的策略，先支付7元，剩余5元，再支付5元，总共需要使用2个货币。 但是，更优的策略是先支付4元，剩余8元，再支付4元和4元，总共需要使用3个货币。 因此，对于B国货币体制，最大面值优先支付的策略不成立。
四、最小平均等待时间问题
问题描述：有n个顾客需要在同一台机器上执行任务，每个顾客需要的时间不同，已知每个顾客需要的时间和到达时间，假设每个顾客到达时立即执行任务，问如何安排任务顺序，才能使平均等待时间最小。 贪心算法的思路：按照每个顾客需要的时间从小到大排序，依次执行任务，计算每个顾客的等待时间，求平均等待时间。
证明：
- 贪心选择性质成立 假设选择的任务序列为I1、I2、I3……Im，按照每个顾客需要的时间从小到大排序，依次执行任务。对于任意一个任务Ix (1≤x≤m-1)，如果Ix的需要时间小于Im，那么Ix的需要时间一定小于Im，否则Ix就会被选择而不是Im。因此，我们可以将Im替换成Ix，得到一个不劣解。因此，贪心选择性质成立。
- 最优子结构性质成立 假设S是最优解，其中选择的任务序列为I1、I2、I3……Im。假设其中一个任务Ij（1≤j≤m-1）被替换成了Ii（i>j），那么替换后的平均等待时间为： T' = (T_j + t_i + t_j) / n + (T_i - t_i) / (n - 1) 其中，T_i是在Ii前面的任务的等待时间之和，t_i是Ii需要的时间，T_j是在Ij前面的任务的等待时间之和，t_j是Ij需要的时间。 如果将Ij替换成Ii，那么Ij将会在Ii后面执行，所以T_i和T_j都会增加t_j，因此： T' - T = (t_j - t_i) / n + (T_j - T_i - t_j) / (n - 1) 因为t_i < t_j，所以T' - T < 0，即替换后得到的解比原来的解更优。因此，最优子结构性质成立。 因此，按照每个顾客需要的时间从小到大排序，依次执行任务的贪心算法得到的解是最优解。
本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！