题目

给定一组多个（$n$）物品，每种物品都有自己的重量（$w_i$）和价值（$v_i$），在限定的总重量/总容量（$C$）内，选择其中若干个（也即每种物品可以选0个或1个），求能取得的最大价值。

用更抽象的话说，给定正整数$1\le w_i\le n,1\le v_i\le n,1\le C\le n$，求： $$max\sum _{i=1}^n{x}_i{v}_i,s.t.\sum _{i=1}^n{x}_i{w}_i\le C,x\in \{0,1\}$$

解法

动态规划

定义$dp(i,w)$为在前i个物品中筛选出总重量不超过w的最大价值。

转移方程：

对于第i个物品，有两种做法：

把它放入背包，则$dp(i,w)=dp(i-1,w-w_i)+v_i$，即先在$i-1$个物品中以最大价值筛选出总重量不超过$w-w_i$的物品，再加上第$i$个物品的价值$v_i$。不把它放入背包，则$dp(i,w)=dp(i-1,w)$，即在负重为$w$时，从$i$个物品中筛选和从$i-1$个物品中筛选的结果是一样的，因为第i个不放入背包中。

当$w_i>w$时，第$i$个物品不可能放入背包中，此时$dp(i,w)$只能取第二种做法。当$w_i\le w$时，需要比较两种做法哪一种能获取较高的价值。得到转移方程：

$$dp(i,w)=\{\begin{array}{ll}0& i=0\\ 0& w=0\\ dp(i-1,w)& w_i>w\\ max\{dp(i-1,w-w_i)+v_i,dp(i-1,w)\}& otherwise\end{array}$$

代码（C++）：

/** * @param itemCount 物品个数 * @param weight 物品重量，weight[i]表示第i个物品的重量（i从1开始） * @param value 物品价值，value[i]表示第i个物品的价值（i从1开始） * @param maxLoad 背包的最大负重 */ int maxValue(int itemCount, vector< int > weight, vector< int > value, int maxLoad) { vector< vector< int > > dp(itemCount + 1, vector< int >(maxLoad + 1, 0)); // dp[i][j]表示从第1个到第i个物品中选择不超过重量j的最大总价值 for (int i = 1; i <= itemCount; i++) { for (int j = 1; j <= maxLoad; j++) { if (weight[i] > j) dp[i][j] = dp[i - 1][j]; // 不选 else { int temp1 = dp[i - 1][j]; int temp2 = dp[i - 1][j - weight[i]] + value[i]; dp[i][j] = temp1 > temp2 ? temp1 : temp2; } } } return dp[itemCount][maxLoad]; }

扩展

通过这个dp数组求出选择的物品编号：

从$i=n,j=C$开始看，若$dp(i-1,j)=dp(i,j)$，则表示第$i$个物品没有被选择，则从$dp(i-1,j)$继续寻找。如果$dp(i-1,j)\ne dp(i,j)$，则表示第$i$个物品被选择，下一步从$dp(i-1,j-w_i)$继续寻找。

/** * @param dp 求最大价值时产生的动态规划数组dp * @param weight 物体重量数组 * @param itemCount 物体个数 * @param maxLoad 背包最大负重 */ vector< int > findItems(vector< vector< int > > dp, vector< int > weight, int itemCount, int maxLoad) { int i = itemCount, j = maxLoad; vector< int > res; while (i > 0 && j > 0) { if (dp[i - 1][j] < dp[i][j]) { res.push_back(i); i--; j -= weight[i]; } else { i--; } } return res; }

本片记录总结自： 【动态规划】01背包问题 - 弗兰克的猫 - 开发者的网上家园 0-1背包问题的动态规划算法 - 知乎