问题描述

给定n种物品和一背包。物品i的重量是wi，其价值为vi，背包的容量为C。问：应如何选择装入背包的物品，使得装入背包中物品的总价值最大？

算法设计分析

背包问题要求达到物品总价值的最优化，每一次选择作为一个阶段，根据前一个阶段的解可以求解出后一个阶段的解。定义状态F[i,y]，表示剩余容量为y，剩余物品为i, i+1, i+2 ,…, n的最优解。所以：

（2）式便是状态转移方程，而（1）式则是边界条件。

例如：假定n=5，物品收益p=[6,3,5,4,6]，物品重量w=[2,2,6,5,4]，且背包容量c=10。

要求的F[1, 10]是整个问题的解，F[1,10]=max{F[2, 10], F[2, 8]+6}，依次类推。调用关系用解空间树表示出来：

每个节点用y值来标识，即F[i,y]，其左孩子表示不选择物品i，得到F[i+1,y]；右孩子表示选择物品i，得到F[i+1,y-wi]+pi；从图中可以看出，对于F[3,8],F[4,8],F[4,2],F[5,8],F[5,2]的有重复计算。对于这种重叠子问题的计算，所以我们可以通过使用一张表来保存数值。该表可以使用哈希表（查找时间O(1)），也可以用二叉查找树查找时间O(logn)表示。此处，由于i和y的值为整数，且数值不大，我们采用二维数组整型F[i][y] 表示，数组元素初始化为-1。

C++实现

// global variables int numberOfObjects; //物品数量 int *weight; //weight[1:numberOfObjects] 物品重量 int *profit; //profit[1:numberOfObjects] 物品收益 int knapsackCore(int i, int capacity, int **F); void traceback(int capacity, int *bestPacking, int **F); int knapsack(int *theProfit, int *theWeight, int theNumberOfObjects, int capacity, int *bestPacking) { if (!theProfit || !theWeight || !bestPacking || theNumberOfObjects <= 0 || capacity <= 0) return -1; numberOfObjects = theNumberOfObjects; profit = theProfit; weight = theWeight; //创建二维数组并初始化为-1 int **F = new int*[numberOfObjects + 1]; for (int i = 0; i <= numberOfObjects; ++i) F[i] = new int[capacity + 1]; for (int i = 1; i <= numberOfObjects; ++i) fill(F[i], F[i] + capacity + 1, -1); //计算最大收益值 int maxProfit = knapsackCore(1, capacity, F); //回溯记录解向量 traceback(capacity, bestPacking, F); //释放二维数组内存 for (int i = 0; i <= numberOfObjects; ++i) delete[] F[i]; delete[] F; F = nullptr; return maxProfit; } //背包问题的递归函数 int knapsackCore(int i, int capacity, int **F) { //检查是否已经计算过 if (F[i][capacity] >= 0) return F[i][capacity]; //未计算过 //公式（1） if (i == numberOfObjects) { F[i][capacity] = (capacity < weight[numberOfObjects] ? 0 : profit[numberOfObjects]); return F[i][capacity]; } //公式（2） if (capacity < weight[i]) F[i][capacity] = knapsackCore(i + 1, capacity, F); else F[i][capacity] = max(knapsackCore(i + 1, capacity, F), knapsackCore(i + 1, capacity - weight[i], F) + profit[i]); return F[i][capacity]; } //沿着数组回溯确定背包中的物品 void traceback(int capacity, int *bestPacking, int **F) { for (int i = 1; i < numberOfObjects; ++i) { if (F[i][capacity] == F[i + 1][capacity]) bestPacking[i] = 0; else { bestPacking[i] = 1; capacity -= weight[i]; } } //i == numberOfObjest bestPacking[numberOfObjects] = (F[numberOfObjects][capacity] > 0 ? 1 : 0); }