贪心算法应用于具有最优子结构性质的背包问题

背包问题的最优子结构性质 若它的一个最优解X包含物品j，则从该最优解X拿走所含的物品j的那部分重量w[j]，则问题变为： 给定n-1个物品1,2,…,j-1,j+1,…,n，以及容量为W-w[j]的背包，则X’=X-{j}是这一问题的最优解。