动态规划在背包问题的应用

动态规划在背包问题的应用一、动态规划概述

动态规划（DynamicProgramming，DP）是一种通过将复杂问题分解为子问题并存储子问题解来优化递归算法的算法思想。它适用于具有以下特征的优化问题：

1.最优子结构：问题的最优解包含子问题的最优解。

2.重叠子问题：不同决策路径可能重复计算相同的子问题。

动态规划通常使用表格（一维或二维）存储中间结果，避免重复计算，显著提高效率。

二、背包问题及其分类

背包问题是一类典型的优化问题，通常描述为：给定一组物品，每个物品有重量和价值，背包有最大承重限制，如何选择物品装入背包，使背包内物品总价值最大，同时不超过承重限制。

（一）背包问题分类

1.0/1背包问题：每个物品只能选择0个或1个。

2.完全背包问题：每个物品可以无限次选择。

3.多重背包问题：每个物品有数量限制，可以选择0个或多个。

本节主要讨论0/1背包问题，其他类型可类似扩展。

三、0/1背包问题的动态规划解法

（一）问题定义

-输入：

-物品数量\(n\)

-背包最大承重\(W\)

-每个物品的重量\(w[i]\)和价值\(v[i]\)

-输出：背包能装下的最大价值。

（二）动态规划状态定义

定义二维数组\(dp[i][j]\)表示：

-状态含义：前\(i\)个物品，背包容量为\(j\)时能装下的最大价值。

（三）状态转移方程

对于第\(i\)个物品，有两种选择：

1.不选择第\(i\)个物品：

\(dp[i][j]=dp[i-1][j]\)

2.选择第\(i\)个物品（前提是\(j\geqw[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])\]

（四）算法步骤

1.初始化：

-\(dp[0][j]=0\)：没有物品时，价值为0。

-\(dp[i][0]=0\)：背包容量为0时，价值为0。

2.填充表格（按行或按列顺序遍历）：

-对于每个物品\(i\)和容量\(j\)，计算\(dp[i][j]\)。

3.结果：

-最终答案为\(dp[n][W]\)。

（五）空间优化

由于每次计算仅依赖上一行数据，可以将二维数组优化为一维数组，降低空间复杂度。

四、示例计算

假设：

-物品数量\(n=4\)

-背包容量\(W=7\)

-物品重量\(w=[3,2,5,1]\)

-物品价值\(v=[10,5,15,10]\)

（一）动态规划表格填充

|物品|容量|0|1|2|3|4|5|6|7|

|------|-------|---|---|---|---|---|---|---|---|

|0|0|0|0|0|0|0|0|0|0|

|1|0|0|0|0|0|0|0|0|0|

|1|1|0|0|0|0|0|0|0|0|

|1|2|0|0|0|0|0|0|0|0|

|1|3|0|0|0|5|5|5|5|5|

|1|4|0|0|0|5|5|5|5|5|

|1|5|0|0|5|5|5|10|10|10|

|1|6|0|0|5|5|10|10|10|10|

|1|7|0|0|5|10|10|10|15|15|

（二）最终结果

最大价值为\(dp[4][7]=15\)，对应选择物品2（价值15，重量5）。

五、总结

动态规划通过分解子问题并存储结果，有效解决了背包问题的优化需求。关键在于：

1.明确状态定义和转移方程。

2.选择合适的表格或空间优化方式。

3.注意边界条件的处理。

类似方法可扩展到其他组合优化问题。

三、0/1背包问题的动态规划解法（续）

（一）动态规划状态定义（详细说明）

动态规划的核心在于将原问题转化为子问题。对于0/1背包问题，定义：

-状态表示：用二维数组\(dp[i][j]\)表示“前\(i\)个物品”在“背包容量为\(j\)时”所能获得的最大价值。

-维度解释：

-\(i\)：物品索引，从0到\(n-1\)（假设物品编号从0开始）。

-\(j\)：当前背包剩余容量，从0到\(W\)（\(W\)为背包总容量）。

-状态含义：

-\(dp[i][j]\)存储的是基于前\(i\)个物品和当前背包容量\(j\)的最优解（即最大价值）。

-最终答案为\(dp[n][W]\)，即考虑所有\(n\)个物品且背包容量为\(W\)时的最大价值。

（二）状态转移方程（深入解析）

状态转移是动态规划的关键，其本质是选择当前物品的最优决策。对于第\(i\)个物品，有两种选择：

1.不选择第\(i\)个物品：

-此时，背包容量不变，仍考虑前\(i-1\)个物品。

-状态转移：\(dp[i][j]=dp[i-1][j]\)

-解释：如果不选第\(i\)个物品，最大价值直接继承自前\(i-1\)个物品在容量\(j\)下的最大价值。

2.选择第\(i\)个物品：

-前提条件：当前背包容量\(j\)必须足够装下第\(i\)个物品（即\(j\geqw[i]\)）。

-操作：

-将第\(i\)个物品装入背包，消耗容量\(w[i]\)。

-剩余容量为\(j-w[i]\)，此时考虑前\(i-1\)个物品的最大价值，并加上第\(i\)个物品的价值\(v[i]\)。

-状态转移：\(dp[i][j]=dp[i-1][j-w[i]]+v[i]\)

-解释：选择第\(i\)个物品后，最大价值等于“剩余容量\(j-w[i]\)下的最大价值”加上“当前物品价值\(v[i]\)”。

3.决策选择：

-对于当前状态\(dp[i][j]\)，需要比较上述两种选择的结果，取较大值：

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

-逻辑：在容量\(j\)下，对于第\(i\)个物品，最优策略是“不选”或“选”，选哪个取决于哪种方式带来的价值更大。

（三）算法步骤（分步详解）

动态规划算法的实现分为以下几步：

(1)初始化表格

-创建二维数组\(dp[n+1][W+1]\)，所有元素初始化为0。

-原因：

-\(dp[0][j]=0\)：没有物品时（\(i=0\)），无论容量多少，价值都为0。

-\(dp[i][0]=0\)：容量为0时（\(j=0\)），无法装任何物品，价值为0。

-注意：索引从0开始，因此需要\(dp[n+1][W+1]\)以覆盖所有情况。

(2)填充表格（按行或按列遍历）

-遍历顺序：通常按物品编号\(i\)从小到大，背包容量\(j\)从小到大遍历。

-每一步的操作：

-对于当前物品\(i\)和当前容量\(j\)，根据状态转移方程计算\(dp[i][j]\)：

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

-条件判断：

-如果\(j<w[i]\)，则无法选择第\(i\)个物品（容量不足），此时\(dp[i][j]=dp[i-1][j]\)。

-如果\(j\geqw[i]\)，则比较“不选”和“选”两种情况。

-示例：

-以第2个物品（\(i=1\)）、容量\(j=3\)为例：

-\(j<w[1]\)（即3<2）？否，继续计算。

-\(dp[1][3]=\max(dp[0][3],dp[0][3-2]+v[1])\)

-\(dp[1][3]=\max(0,0+5)=5\)

(3)获取最终结果

-最终最大价值存储在\(dp[n][W]\)中。

-可选：如果需要知道具体选择了哪些物品，可以回溯表格：

-从\(dp[n][W]\)开始，检查\(dp[i][j]\)和\(dp[i-1][j]\)的关系：

-如果\(dp[i][j]=dp[i-1][j]\)，则第\(i\)个物品未被选择。

-如果\(dp[i][j]=dp[i-1][j-w[i]]+v[i]\)，则第\(i\)个物品被选择，记录该物品。

-继续回溯\(i-1\)，直到\(i=0\)。

（四）空间优化（降维打击）

二维数组虽然直观，但空间复杂度为\(O(nW)\)，对于大\(n\)或\(W\)可能不高效。通过观察状态转移方程，可以发现：

-计算\(dp[i][j]\)只依赖于第\(i-1\)行的数据（即\(dp[i-1][\cdot]\)）。

-因此，可以将二维数组优化为一维数组，按容量\(j\)从小到大的顺序计算。

优化步骤：

1.创建一维数组\(dp[W+1]\)，初始化为0。

2.按物品遍历：对于每个物品\(i\)，从大到小更新\(dp[j]\)（即从\(W\)到\(w[i]\)逐步减少容量）：

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

-原因：按容量从大到小更新可以避免重复计算。

3.最终结果仍为\(dp[W]\)。

示例：

-物品：\(w=[3,2,5,1]\),\(v=[10,5,15,10]\),\(W=7\)。

-初始化：\(dp=[0,0,0,0,0,0,0,0]\)。

-第1个物品（\(i=0\)）：

-更新\(j=7,6,5,4,3\)：

-\(dp[7]=\max(0,dp[4]+10)=10\)

-\(dp[6]=\max(0,dp[4]+10)=10\)

-\(dp[5]=\max(0,dp[3]+10)=10\)

-\(dp[4]=\max(0,dp[1]+10)=10\)

-\(dp[3]=\max(0,dp[0]+10)=10\)

-更新后：\(dp=[0,0,0,0,10,10,10,10]\)。

-第2个物品（\(i=1\)）：

-更新\(j=7,6,5,4\)：

-\(dp[7]=\max(10,dp[5]+5)=15\)

-\(dp[6]=\max(10,dp[4]+5)=15\)

-\(dp[5]=\max(10,dp[3]+5)=15\)

-\(dp[4]=\max(10,dp[2]+5)=10\)

-更新后：\(dp=[0,0,0,5,10,15,15,15]\)。

-最终结果：\(dp[7]=15\)。

（五）时间与空间复杂度

-时间复杂度：\(O(nW)\)

-每个物品和每个容量都计算一次。

-空间复杂度：

-二维数组：\(O(nW)\)。

-一维数组优化后：\(O(W)\)。

四、代码实现（伪代码示例）

```pseudo

functionknapsack_01(weights,values,W):

n=length(weights)

dp=arrayofsize(W+1)initializedto0

forifrom0ton-1:

forjfromWdowntoweights[i]:

dp[j]=max(dp[j],dp[j-weights[i]]+values[i])

returndp[W]

五、应用场景与扩展

（一）典型应用场景

0/1背包问题适用于资源有限、选择离散的场景，例如：

1.购物选择：在预算内购买商品，最大化总价值。

2.任务调度：在时间或资源限制下，选择任务组合以最大化收益。

3.基因组合：在有限资源下，选择基因片段组合以最大化表达效果。

（二）其他背包问题扩展

动态规划思想可推广至其他背包类型：

1.完全背包问题：每个物品可无限次选择。

-状态转移：\(dp[j]=\max(dp[j],dp[j-w[i]]+v[i])\)

-需按物品遍历，但无需逆序更新。

2.多重背包问题：每个物品有数量限制\(c[i]\)。

-可分解为多个0/1背包问题合并。

-也可用一维数组，但需调整遍历策略。

（三）优化技巧

1.排序：按价值密度（\(v[i]/w[i]\)）降序排列物品，可提高填充效率。

2.剪枝：如果当前物品无法提供更大价值，提前终止遍历。

六、总结

动态规划通过将问题分解为子问题并存储结果，有效解决了背包问题的优化需求。关键在于：

1.明确状态定义和转移方程。

2.选择合适的表格或空间优化方式。

3.注意边界条件的处理。

4.可通过排序或剪枝进一步优化。

类似方法可扩展到其他组合优化问题，如旅行商问题、最长公共子序列等。

一、动态规划概述

动态规划（DynamicProgramming，DP）是一种通过将复杂问题分解为子问题并存储子问题解来优化递归算法的算法思想。它适用于具有以下特征的优化问题：

1.最优子结构：问题的最优解包含子问题的最优解。

2.重叠子问题：不同决策路径可能重复计算相同的子问题。

动态规划通常使用表格（一维或二维）存储中间结果，避免重复计算，显著提高效率。

二、背包问题及其分类

背包问题是一类典型的优化问题，通常描述为：给定一组物品，每个物品有重量和价值，背包有最大承重限制，如何选择物品装入背包，使背包内物品总价值最大，同时不超过承重限制。

（一）背包问题分类

1.0/1背包问题：每个物品只能选择0个或1个。

2.完全背包问题：每个物品可以无限次选择。

3.多重背包问题：每个物品有数量限制，可以选择0个或多个。

本节主要讨论0/1背包问题，其他类型可类似扩展。

三、0/1背包问题的动态规划解法

（一）问题定义

-输入：

-物品数量\(n\)

-背包最大承重\(W\)

-每个物品的重量\(w[i]\)和价值\(v[i]\)

-输出：背包能装下的最大价值。

（二）动态规划状态定义

定义二维数组\(dp[i][j]\)表示：

-状态含义：前\(i\)个物品，背包容量为\(j\)时能装下的最大价值。

（三）状态转移方程

对于第\(i\)个物品，有两种选择：

1.不选择第\(i\)个物品：

\(dp[i][j]=dp[i-1][j]\)

2.选择第\(i\)个物品（前提是\(j\geqw[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])\]

（四）算法步骤

1.初始化：

-\(dp[0][j]=0\)：没有物品时，价值为0。

-\(dp[i][0]=0\)：背包容量为0时，价值为0。

2.填充表格（按行或按列顺序遍历）：

-对于每个物品\(i\)和容量\(j\)，计算\(dp[i][j]\)。

3.结果：

-最终答案为\(dp[n][W]\)。

（五）空间优化

由于每次计算仅依赖上一行数据，可以将二维数组优化为一维数组，降低空间复杂度。

四、示例计算

假设：

-物品数量\(n=4\)

-背包容量\(W=7\)

-物品重量\(w=[3,2,5,1]\)

-物品价值\(v=[10,5,15,10]\)

（一）动态规划表格填充

|物品|容量|0|1|2|3|4|5|6|7|

|------|-------|---|---|---|---|---|---|---|---|

|0|0|0|0|0|0|0|0|0|0|

|1|0|0|0|0|0|0|0|0|0|

|1|1|0|0|0|0|0|0|0|0|

|1|2|0|0|0|0|0|0|0|0|

|1|3|0|0|0|5|5|5|5|5|

|1|4|0|0|0|5|5|5|5|5|

|1|5|0|0|5|5|5|10|10|10|

|1|6|0|0|5|5|10|10|10|10|

|1|7|0|0|5|10|10|10|15|15|

（二）最终结果

最大价值为\(dp[4][7]=15\)，对应选择物品2（价值15，重量5）。

五、总结

动态规划通过分解子问题并存储结果，有效解决了背包问题的优化需求。关键在于：

1.明确状态定义和转移方程。

2.选择合适的表格或空间优化方式。

3.注意边界条件的处理。

类似方法可扩展到其他组合优化问题。

三、0/1背包问题的动态规划解法（续）

（一）动态规划状态定义（详细说明）

动态规划的核心在于将原问题转化为子问题。对于0/1背包问题，定义：

-状态表示：用二维数组\(dp[i][j]\)表示“前\(i\)个物品”在“背包容量为\(j\)时”所能获得的最大价值。

-维度解释：

-\(i\)：物品索引，从0到\(n-1\)（假设物品编号从0开始）。

-\(j\)：当前背包剩余容量，从0到\(W\)（\(W\)为背包总容量）。

-状态含义：

-\(dp[i][j]\)存储的是基于前\(i\)个物品和当前背包容量\(j\)的最优解（即最大价值）。

-最终答案为\(dp[n][W]\)，即考虑所有\(n\)个物品且背包容量为\(W\)时的最大价值。

（二）状态转移方程（深入解析）

状态转移是动态规划的关键，其本质是选择当前物品的最优决策。对于第\(i\)个物品，有两种选择：

1.不选择第\(i\)个物品：

-此时，背包容量不变，仍考虑前\(i-1\)个物品。

-状态转移：\(dp[i][j]=dp[i-1][j]\)

-解释：如果不选第\(i\)个物品，最大价值直接继承自前\(i-1\)个物品在容量\(j\)下的最大价值。

2.选择第\(i\)个物品：

-前提条件：当前背包容量\(j\)必须足够装下第\(i\)个物品（即\(j\geqw[i]\)）。

-操作：

-将第\(i\)个物品装入背包，消耗容量\(w[i]\)。

-剩余容量为\(j-w[i]\)，此时考虑前\(i-1\)个物品的最大价值，并加上第\(i\)个物品的价值\(v[i]\)。

-状态转移：\(dp[i][j]=dp[i-1][j-w[i]]+v[i]\)

-解释：选择第\(i\)个物品后，最大价值等于“剩余容量\(j-w[i]\)下的最大价值”加上“当前物品价值\(v[i]\)”。

3.决策选择：

-对于当前状态\(dp[i][j]\)，需要比较上述两种选择的结果，取较大值：

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

-逻辑：在容量\(j\)下，对于第\(i\)个物品，最优策略是“不选”或“选”，选哪个取决于哪种方式带来的价值更大。

（三）算法步骤（分步详解）

动态规划算法的实现分为以下几步：

(1)初始化表格

-创建二维数组\(dp[n+1][W+1]\)，所有元素初始化为0。

-原因：

-\(dp[0][j]=0\)：没有物品时（\(i=0\)），无论容量多少，价值都为0。

-\(dp[i][0]=0\)：容量为0时（\(j=0\)），无法装任何物品，价值为0。

-注意：索引从0开始，因此需要\(dp[n+1][W+1]\)以覆盖所有情况。

(2)填充表格（按行或按列遍历）

-遍历顺序：通常按物品编号\(i\)从小到大，背包容量\(j\)从小到大遍历。

-每一步的操作：

-对于当前物品\(i\)和当前容量\(j\)，根据状态转移方程计算\(dp[i][j]\)：

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

-条件判断：

-如果\(j<w[i]\)，则无法选择第\(i\)个物品（容量不足），此时\(dp[i][j]=dp[i-1][j]\)。

-如果\(j\geqw[i]\)，则比较“不选”和“选”两种情况。

-示例：

-以第2个物品（\(i=1\)）、容量\(j=3\)为例：

-\(j<w[1]\)（即3<2）？否，继续计算。

-\(dp[1][3]=\max(dp[0][3],dp[0][3-2]+v[1])\)

-\(dp[1][3]=\max(0,0+5)=5\)

(3)获取最终结果

-最终最大价值存储在\(dp[n][W]\)中。

-可选：如果需要知道具体选择了哪些物品，可以回溯表格：

-从\(dp[n][W]\)开始，检查\(dp[i][j]\)和\(dp[i-1][j]\)的关系：

-如果\(dp[i][j]=dp[i-1][j]\)，则第\(i\)个物品未被选择。

-如果\(dp[i][j]=dp[i-1][j-w[i]]+v[i]\)，则第\(i\)个物品被选择，记录该物品。

-继续回溯\(i-1\)，直到\(i=0\)。

（四）空间优化（降维打击）

二维数组虽然直观，但空间复杂度为\(O(nW)\)，对于大\(n\)或\(W\)可能不高效。通过观察状态转移方程，可以发现：

-计算\(dp[i][j]\)只依赖于第\(i-1\)行的数据（即\(dp[i-1][\cdot]\)）。

-因此，可以将二维数组优化为一维数组，按容量\(j\)从小到大的顺序计算。

优化步骤：

1.创建一维数组\(dp[W+1]\)，初始化为0。

2.按物品遍历：对于每个物品\(i\)，从大到小更新\(dp[j]\)（即从\(W\)到\(w[i]\)逐步减少容量）：

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

-原因：按容量从大到小更新可以避免重复计算。

3.最终结果仍为\(dp[W]\)。

示例：

-物品：\(w=[3,2,5,1]\),\(v=[10,5,15,10]\),\(W=7\)。

-初始化：\(dp=[0,0,0,0,0,0,0,0]\)。

-第1个物品（\(i=0\)）：

-更新\(j=7,6,5,4,3\)：

-\(dp[7]=\max(0,dp[4]+10)=10\)

-\(dp[6]=\max(0,dp[4]+10)=10\)

-\(dp[5]=\max(0,dp[3]+10)=10\)

-\(dp[4]=\max(0,dp[1]+10)=10\)

-\(dp[3]=\max(0,dp[0]+10)=10\)

-更新后：\(dp=[0,0,0,0,10,10,10,10