0-1背包问题
问题描述
给定n个重量为w1,...,wn，价值为v1,...,vn的物品和一个承重量为W的背包，求这些物品中最有价值的一个子集，并且要能够装到背包中。
动态规划算法
为了设计一个动态规划算法，需要推导出一个递推关系，用较小实例的解的形式来表示背包问题的实例的解。让我们来考虑一个由前i个物品(1<=i<=n)定义的一个实例，物品的重量分别为w1,...,wi，价值分别为v1,...,vi，背包的承重量为j(1<=j<=W)。设V[i,j]为该实例的最优解的物品的总价值。可以把前i个物品中能够放进承重量为j的背包中的子集分成两个类别：包括第i各物品的子集和不包括第i个物品的子集。然后有下面的结论：
- 根据定义，在不包括第i个物品的子集中，最优子集的价值是V[i-1,j].
- 在包括第i个物品的子集中(因此，j-wi>=0)，最优子集是由该物品和前i-1个物品中能够放进承重量为j-wi的背包的最优子集组成。这种最优子集的总价值等于vi+V[i-1,j-wi]。
因此，在前i个物品中最优解的总价值等于这两个价值中的较大值。当然，如果第i个物品不能放进背包，从前i个物品中选出的最优子集的总价值等于从前i-1个物品中选出的最优子集的总价值。这个结果导致了下面这个递推式：
当j-wi>=0,V[i,j]=max{V[i-1,j],vi+V[i-1,j-wi]}
当j-wi<0,V[i,j]=V[i-1,j]