贪心算法证明 反证法

贪心算法是一种常用的算法思想，它通常用于求解最优化问题。贪心算法的基本思想是：每一步都选择当前状态下最优的解，最终得到全局最优解。但是，贪心算法并不是所有问题都适用，有些问题需要进行证明才能确定贪心算法的正确性。

其中，反证法是一种常用的证明方法。反证法的基本思想是：假设所要证明的命题不成立，然后推导出一个矛盾的结论，从而证明原命题成立。

在贪心算法中，反证法通常用于证明贪心选择性质和最优子结构性质。具体来说，假设贪心算法得到的解不是最优解，然后推导出一个矛盾的结论，从而证明贪心算法得到的解是最优解。

举个例子，假设有一个背包问题，要求在背包容量为C的情况下，选择一些物品放入背包中，使得背包中物品的总价值最大。每个物品有两个属性：重量w和价值v。贪心算法可以选择每次选择单位重量价值最大的物品放入背包中。我们可以使用反证法来证明这个贪心算法的正确性：

假设贪心算法得到的解不是最优解，即存在一种更优的解。我们假设这个更优的解选择了物品i和物品j，但是贪心算法没有选择物品j，而是选择了物品k。那么我们可以得到以下两个不等式：

v[i]/w[i] > v[j]/w[j] （物品i的单位重量价值大于物品j的单位重量价值）
v[i]/w[i] < v[k]/w[k] （物品i的单位重量价值小于物品k的单位重量价值）

将这两个不等式相乘，得到：

v[i]*v[k] > v[j]*w[i]

由于v[i]、v[j]、w[i]、w[j]都是正数，所以上式成立。但是，我们知道贪心算法选择物品i和物品k的总价值一定大于选择物品i和物品j的总价值，因为：

v[i]*w[k] + v[k]*w[i] > v[i]*w[j] + v[j]*w[i]
这与上式矛盾，因此假设不成立，贪心算法得到的解是最优解。