动态规划（7）：背包问题

引言

背包问题是动态规划中最经典、最重要的问题类型之一，它不仅在算法竞赛中频繁出现，也在实际应用中有着广泛的用途。从资源分配到投资组合优化，从生产计划到网络路由，背包问题的思想几乎无处不在。正因如此，背包问题被誉为动态规划的"必修课"，掌握背包问题的解法对于理解和应用动态规划至关重要。

01背包问题详解

问题描述

01背包是最基础的背包问题，其描述如下：

有N件物品和一个容量为V的背包。第i件物品的重量是w[i]，价值是v[i]。求解将哪些物品装入背包，可使这些物品的总重量不超过背包容量，且总价值最大。

名称"01"的由来是指对每件物品只有两种选择：要么选（用1表示），要么不选（用0表示）。

问题分析

01背包问题是一个典型的动态规划问题，我们可以通过以下步骤来解决：

1. 状态定义：设dp[i][j]表示考虑前i件物品，背包容量为j时能获得的最大价值。

2. 状态转移方程：对于第i件物品，有两种选择：

   • 不选择第i件物品：dp[i][j] = dp[i-1][j]
   • 选择第i件物品（前提是背包容量足够）：dp[i][j] = dp[i-1][j-w[i]] + v[i]

   综合这两种情况，状态转移方程为：

   dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i])  (j >= w[i])
   dp[i][j] = dp[i-1][j]  (j < w[i])
   

3. 初始状态：dp[0][j] = 0，表示没有物品可选时，无论背包容量多大，价值都为0。

4. 最终结果：dp[N][V]，表示考虑所有N件物品，背包容量为V时能获得的最大价值。

空间优化

上述解法的空间复杂度是O(N*V)，但我们可以通过滚动数组的技巧将空间复杂度优化到O(V)。

观察状态转移方程可以发现，计算dp[i][j]时只需要用到dp[i-1][j]和dp[i-1][j-w[i]]，也就是说，当前状态只与上一行的状态有关。因此，我们可以使用一维数组dp[j]来代替二维数组，其中dp[j]表示背包容量为j时能获得的最大价值。

但是，这里有一个关键点：为了避免在一次迭代中重复使用更新后的状态，我们需要从大到小遍历背包容量j。这样可以确保在计算dp[j]时，dp[j-w[i]]保存的仍然是上一轮的状态。

优化后的状态转移方程：

dp[j] = max(dp[j], dp[j-w[i]] + v[i])  (j >= w[i])

代码实现

// 01背包问题的一维动态规划解法
int knapsack01(int N, int V, vector<int>& w, vector<int>& v) {vector<int> dp(V + 1, 0);for (int i = 0; i < N; i++) {for (int j = V; j >= w[i]; j--) {dp[j] = max(dp[j], dp[j - w[i]] + v[i]);}}return dp[V];
}

实际应用

01背包问题在实际中有许多应用场景，例如：

1. 资源分配：在有限资源下，如何选择项目以最大化收益。
2. 投资决策：在有限资金下，如何选择投资组合以最大化回报。
3. 货物装载：在有限空间内，如何选择货物以最大化价值。
4. 任务调度：在有限时间内，如何选择任务以最大化完成的任务价值。

完全背包问题

问题描述

完全背包问题是01背包问题的一个变种。区别在于：01背包中每种物品只有一件，而完全背包中每种物品有无限件可用。

具体描述：有N种物品和一个容量为V的背包。第i种物品的重量是w[i]，价值是v[i]，每种物品有无限件可用。求解将哪些物品装入背包，可使这些物品的总重量不超过背包容量，且总价值最大。

问题分析

完全背包问题的分析思路与01背包类似，但状态转移方程有所不同：

1. 状态定义：设dp[i][j]表示考虑前i种物品，背包容量为j时能获得的最大价值。

2. 状态转移方程：对于第i种物品，可以选择0件、1件、2件…直到背包容量不足。但这样枚举会导致时间复杂度过高。我们可以通过优化状态转移方程来避免这种枚举：

   dp[i][j] = max(dp[i-1][j], dp[i][j-w[i]] + v[i])  (j >= w[i])
   

   注意这里与01背包的区别：在选择第i种物品时，我们使用的是dp[i][j-w[i]]而不是dp[i-1][j-w[i]]，因为我们可以重复选择同一种物品。

3. 初始状态：dp[0][j] = 0。

4. 最终结果：dp[N][V]。

空间优化

与01背包类似，完全背包也可以使用一维数组进行空间优化。但是，由于状态转移方程的不同，完全背包在遍历背包容量时需要从小到大遍历，而不是从大到小。

优化后的状态转移方程：

dp[j] = max(dp[j], dp[j-w[i]] + v[i])  (j >= w[i])

代码实现