0-1背包问题是这样的：有一个贼在偷窃一家商店时发现有n件物品；第i件物品值value[i]元，重weight[i]斤，假设此处value[i]和weight[i]都是整数。他希望带走的东西越值钱越好，但他的背包中至多只能装下W斤的东西，W为一整数。应该带走哪几样东西？（这个问题之所以称为0-1背包问题，是因为每件物品或被带走，或被留下；小偷不能只带走某个物品的一部分或带走两次以上的同一物品。）
分析：在这个问题中，当我们在考虑是否要把一件物品加到背包中去时，必须对把该物品加进去的子问题的解与不取该物品的子问题的解进行比较。由这种方式形成的问题导致了许多重叠的子问题，这是动态规划的一个特点，所以我们使用动态规划来解决该问题。
解答：该问题的解基于如下的最优子结构。对于容量为volume斤的背包，编号为1到itemAmount的itemAmount个物品，假定i为最优解S中编号最大的物品。那么S' = S - {i}肯定是背包容量为volume - weight[i]斤，编号1到n-1的n-1个物品这种情况下的最优子结构。并且最优解S的价值等于value[i]加上子问题最优解S'的价值。
我们可以使用下面的公式表示这种关系：定义sum[i, j]为，背包容量为j斤，有编号1到i的i个物品这种情况下，最优解的价值，那么
最后一种情况表示，对于i个物品，其最优解的价值有可能包含物品i，这种情况下，它的价值为value[i]加上，背包容量为j - weight[i]，有编号1到i - 1的i - 1个物品的这种情况下，最优解的价值；或者不包含物品i，这种情况下，它的价值就是，背包容量为j，有编号1到i - 1个物品这种情况下，最优解的价值。也就是说，如果盗贼选择物品i，那么他就获得了value[i]的价值，然后他能够从i - 1个物品中选择，不过这时候，背包容量只剩下j - weight[i]，即他可以获得另外sum[i
- 1, j - weight[i]]的价值；另一方面，如果他不选择物品i，那么它能够从i-1个物品中选择，背包容量还是j，即他能够得到sum[i - 1, j]的价值。他需要在这两种方案中选择最好的一种。
该算法以一个价值序列value[0...itemAmount]、一个重量序列weight[0...itemAmout]、物品的数量itemAmount和背包的容量volume为输入。另外在计算过程中，声明了一个二维数组sum[0...itemAmount][0...volume]用于保存最优子结构。算法结束时，sum[itemAmount][volume]包含了盗贼带走的最大值。
#include <cassert>
/**
* The 0-1 knapsack problem
* @arg value - value[i] is the value of item i
* @arg weight - weight[i] is the weight of item i
* @arg itemAmout - the amount of items
* @arg volume - the volume of knapsack
*/
int knapsack01(int value[], int weight[], int itemAmount, int volume)
{
// check if the arguments are valid
assert(value != NULL && weight != NULL && itemAmount > 0 && volume > 0);
/* construct a 2D array whose dimensions are (itemAmount + 1) and (volume + 1)
* define sum[i][j] to be the value of the solution for items 1,...,i and maximum
* weight j.
*/
int **sum = new int*[itemAmount + 1];
for(int i = 0; i <= itemAmount; ++ i)
sum[i] = new int[volume + 1];
/* obviously, if there is no item exists or the volume of knapsack is 0,
* the value also is 0
*/
for(int i = 0; i <= volume; ++ i)
sum[0][i] = 0;
for(int i = 0; i <= itemAmount; ++ i)
sum[i][0] = 0;
for(int i = 1; i <= itemAmount; ++ i)
{
for (int j = 1; j <= volume; ++ j)
{
sum[i][j] = sum[i - 1][j];
/* if we choose item i and the result value of the solution is larger than
* the value of solution in which we don't choose item i, then we choose item i
*/
if(weight[i] <= j && sum[i][j] < (sum[i - 1][j - weight[i]] + value[i]))
sum[i][j] = sum[i - 1][j - weight[i]] + value[i];
}
}
/* the final result is the value of the solution for items 1,...,itemAmount and
* maximum weight volume
*/
int result = sum[itemAmount][volume];
// remember to release the resources
for(int i = 0; i <= itemAmount; ++ i)
delete [](sum[i]);
delete []sum;
return result;
}
上述算法时间复杂度为O(itemAmount*volume):
- 其中O(itemAmount*volume)用于给sum[itemAmount+1][volume+1]赋值：共有(itemAmount+1)(volume+1)项，每项需要O(1)的时间。
测试代码为：
int _tmain(int argc, _TCHAR* argv[])
{
// the item 0 doesn't exist, so assign value[0] and weight[0] to 0
int value[4] = {0, 60, 100, 120};
int weight[4] = {0, 10, 20, 30};
cout << knapsack01(value, weight, 3, 50) << endl;
return 0;
}