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个物品的子集。然后有下面的结论：

1. 根据定义，在不包括第i个物品的子集中，最优子集的价值是V[i-1,j].
2. 在包括第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]

伪代码

Knapsack(w[0...n-1],V[0...n-1],W)
// 用动态规划算法解决0-1背包问题
// 输入：背包的容量W，各物品的重量w及其价值v
// 输出：最大的价值及解集

for i from 0 to W - 1
  v[0][j]<-0  // 当物品个数为0时，价值为0
for i from 0 to n-1
  v[i][0]<-0  // 当承重量为0时，价值为0
for i from 1 to n - 1:
  for j from 1 to W - 1:
    if j <= w[i]:
      v[i][j]<-v[i-1][j]
    else:
      v[i][j]<-max{v[i-1][j],v[i-1][j-w[i]]+Vi}

while r != 0 && c!= 0:
  if v[r][c] != v[r-1][c]:
    Result U r    // 将第r个物品加入到解集中
    c<-c-w[i]
  r<-r-1