分数背包问题贪心证明

分数背包问题的贪心证明基于单位重量价值最大的贪心策略，即优先选择单位重量价值最大的物品放入背包中。证明如下：

假设存在最优解Y=(y1,...,yn)，其中yi表示第i个物品的选择情况，取值为0或1。设X=(x1,...,xn)为贪心算法得到的解，其中xi表示第i个物品的选择情况，取值为0或1。

由于分数背包问题中每个物品都可以分割，因此我们可以将物品按照单位重量价值从大到小排序，然后依次选择单位重量价值最大的物品放入背包中，直到背包装满为止。设第k个物品是第一个不能完全放入背包中的物品，即它的重量为wk，但是只能放入部分物品，放入比例为pk（0<pk<1）。

根据贪心策略，第k个物品的单位重量价值一定大于等于前k-1个物品的单位重量价值，即vk/wk>=vi/wi (1<=i<=k-1)。因此，我们可以将第k个物品分割成pk个物品，每个物品的重量为wi=pk*wk，价值为vi=pk*vk。这样，我们就得到了一个新的解X'，其中第k个物品的选择情况为pk，其余物品的选择情况与X相同。

由于X是贪心算法得到的解，因此它的单位重量价值一定大于等于Y的单位重量价值，即∑(i=1 to n)vi*xi/wi>=∑(i=1 to n)vi*yi/wi。又因为第k个物品的选择情况不同，因此X'与Y的价值一定不同。假设X'的价值大于Y的价值，即∑(i=1 to n)vi*xi/wi>∑(i=1 to n)vi*yi/wi。由于X'是在X的基础上分割第k个物品得到的，因此∑(i=1 to n)xi/wi=∑(i=1 to n)yi/wi，即X和Y的重量相同。因此，我们可以将X'中第k个物品的选择情况改为1，其余物品的选择情况与X相同，得到一个新的解X''。显然，X''的价值不小于X'的价值，因此X''的价值也大于Y的价值，与Y是最优解矛盾。因此，假设不成立，贪心算法得到的解X是最优解。