证明背包问题贪心选择性质

背包问题是一个经典的动态规划问题，可以使用贪心算法来解决。部分背包问题的贪心选择性质可以描述为：每次从Ci,j中选择物品，都是优先考虑选择物品i，且在满足条件1的情况下，Xi越接近1越好。

下面使用数学归纳法证明这一贪心选择性质：

首先，当只有一个物品时，显然贪心算法得到的解是最优解。

假设当物品数为k时，贪心算法得到的解是最优解。

当物品数为k+1时，设物品k+1的重量为wk+1，价值为vk+1。根据贪心选择性质，我们应该优先考虑选择物品k+1，然后再考虑选择其他物品。

设Ai,j表示在前i个物品中选择总重量不超过j的物品的最大价值。则有：

当不选物品k+1时，有Ai,j=Ai-1,j；

当选物品k+1时，有Ai,j=vi+Ai-1,j-wi。

因此，有Ai,j=max{Ai-1,j,vi+Ai-1,j-wi}。

根据假设，当物品数为k时，贪心算法得到的解是最优解，即Ak,j=Pk,j。其中Pk,j表示在前k个物品中选择总重量不超过j的物品的最大价值。

因此，当物品数为k+1时，贪心算法得到的解为：

Pk+1,j=max{Pk,j, vk+Pk,j-wk+1}。

而Ak+1,j=max{Ak,j, vk+Ak,j-wk+1}。

由于Pk,j=Pk-1,j，Ak,j=Ak-1,j，因此有：

Pk+1,j=max{Pk-1,j, vk+Pk-1,j-wk+1}；

Ak+1,j=max{Ak-1,j, vk+Ak-1,j-wk+1}。

因为Pk-1,j≤Ak-1,j，所以Pk+1,j≤Ak+1,j。

因此，当物品数为k+1时，贪心算法得到的解仍然是最优解。

综上所述，部分背包问题的贪心选择性质成立。