## 动态规划（Dynamic Programming）

### 定义

> **动态规划（Dynamic Programming）**：简称 **DP**，是一种求解多阶段决策过程最优化问题的方法。在动态规划中，通过把原问题分解为相对简单的子问题，先求解子问题，再由子问题的解而得到原问题的解。



这里的 Programming 规划并不是编程/编写计算机程序的意思，而是指一种「表格处理方法」，即将每一步计算的结果存储在表格中，供随后的计算查询使用。

### 常用场景：

主要用于求解以时间划分阶段的动态过程的优化问题

动态规划算法通常用于求解具有某种最有性质的问题

### 基本思想/原理

1. 把「原问题」分解为「若干个重叠的子问题」，每个子问题的求解过程都构成一个 **「阶段」**。在完成一个阶段的计算之后，动态规划方法才会执行下一个阶段的计算。
2. 在求解子问题的过程中，按照「自顶向下的记忆化搜索方法」或者「自底向上的递推方法」求解出「子问题的解」，把结果存储在表格中，当需要再次求解此子问题时，直接从表格中查询该子问题的解，从而避免了大量的重复计算。



动态规划与分治法类似，都是通过组合子问题的解来求解原问题。

分治法将问题划分为**互不相交**的子问题，即将问题划分成独立的子问题，递归求解子问题，再将子问题的解组合（合并）起来，求出原问题的解。会重复处理相同、公共的子子问题。

动态规划应用于子问题重叠的情况，即子问题不是独立的情况，各子问题有公共的子子问题，动态规划只需要对每个子子问题求解一次，将其解保存在一个表格中，避免了大量的重复计算。

分治法可以采用记忆化（memoization）方法将求解过的子子问题保存起来，避免重复计算，即自顶向下（top-down）的方法，可称为记忆化自顶向下的动态规划，一般也称为记忆化搜索。

动态规划采用自底向上的递推方法，称为自底向上的动态规划。

自顶向下的分析，自底向上的计算。

 ![image-20260301163159872](https://chenalna.oss-cn-hangzhou.aliyuncs.com/img/image-20260301163159872.png)

### 特征/要素/性质：

1、 最优子结构

2、 重叠子问题

3、 无后效性

4、自底向上的求解方式

还可以根据重叠子问题的特征运用记忆化自顶向下的递归方法进行优化。

#### 最优子结构

前提：有总体最优

结论：有局部最优

大问题的最优解包含了其子问题的最优解。

举个例子，如下图所示，原问题 S={a1,a2,a3,a4}，在 a1步我们选出一个当前最优解之后，问题就转换为求解S子问题 ={a2,a3,a4}。如果原问题 S的最优解可以由「第 a1步得到的局部最优解」和「 S子问题 的最优解」构成，则说明该问题满足最优子结构性质。

也就是说，如果原问题的最优解包含子问题的最优解，则说明该问题满足最优子结构性质。

动态规划通常求解最优化（optimizaiton）问题，有多个可行解，每个解都有一个值，找出一个最优性质（值最小或最大）的解，称这个解为一个最优解（optimial solution）。最优解并不唯一。

#### 重叠子问题

在求解子问题的过程中，有大量的子问题是重复的，一个子问题在下一阶段的决策中可能会被多次用到。如果有大量重复的子问题，那么只需要对其求解一次，然后用表格将结果存储下来，以后使用时可以直接查询，不需要再次求解。

求解问题的第一步描述的是最优解的结构特征：问题的最优解包含子问题的最优解。如果一个问题能够表现出最优子结构特征，那么它可能能够用动态规划求解，当然也可以是其他方法，如贪心相同的子问题，就称作最优化问题具有重叠子问题性质、策略。

 

1、证明问题的一个解是一个选择产生的。这次选择结束后会产生一个或多个的待解决的子问题。

2、给定问题存在一个选择是最优解的方案

3、给定选择后，就能确定具体子问题和这些子问题的特征。

4、利用剪切粘贴技术证明：即某问题的子问题的解不是最优解，就把不是最优解的子问题剪切掉，再将子问题对应的最优解粘贴上。本质就是用最优解对非最优解进行替换，进行调优。

即把运算的结果保存起来，后面用到的时候利用，避免了重复的计算。

#### 无后效性

指的是子问题的解（状态值）只与之前阶段有关，而与后面阶段无关。当前阶段的若干状态值一旦确定，就不再改变，不会再受到后续阶段决策的影响。

即某阶段状态一旦确定，就不受这个状态以后决策的影响。即某状态以后的过程不影响以前的状态。只与当前状态有关。即大问题的解不会影响子问题的解。




举个例子，下图是一个有向无环带权图，我们在求解从 A点到F 点的最短路径问题时，假设当前已知从 A点到D 点的最短路径（2+7=9）。那么无论之后的路径如何选择，都不会影响之前从 A点到D 点的最短路径长度。这就是「无后效性」。

而如果一个问题具有「后效性」，则可能需要先将其转化或者逆向求解来消除后效性，然后才可以使用动态规划算法。

### 求解步骤：

1. 描述一个最优解的结构特征。
2. 递归地定义最优解的值。（建立递归式或动态规划方程）（也叫状态转移方程）
3. 计算最优解的值，通常采用自底向上的方法。
4. 利用计算出的信息构造出一个最优解。

用一个表记录所有已解决的子问题的答案。

第1步到第3步是求解动态规划问题的基础，如果我们仅仅需要最优解的一个值，而不是最优解本身，可以忽略第4步。如果要构造最优解，需要在第3步中维护一些额外信息（记录相关信息）。

评：当 x=a 时，最优解的值为 f(a) ，最优解为 f(x) 。

### 基本思路

如下图所示，我们在使用动态规划方法解决某些最优化问题时，可以将解决问题的过程按照一定顺序（时间顺序、空间顺序或其他顺序）分解为若干个相互联系的「阶段」。然后按照顺序对每一个阶段做出「决策」，这个决策既决定了本阶段的效益，也决定了下一阶段的初始状态。依次做完每个阶段的决策之后，就得到了一个整个问题的决策序列。

这样就将一个原问题分解为了一系列的子问题，再通过逐步求解从而获得最终结果。

![image-20260309132400939](https://chenalna.oss-cn-hangzhou.aliyuncs.com/img/image-20260309132400939.png)

这种前后关联、具有链状结构的多阶段进行决策的问题也叫做「多阶段决策问题」。

通常我们使用动态规划方法来解决问题的基本思路如下：

1. **划分阶段**：将原问题按顺序（时间顺序、空间顺序或其他顺序）分解为若干个相互联系的「阶段」。划分后的阶段⼀定是有序或可排序的，否则问题⽆法求解。
   - 这里的「阶段」指的是⼦问题的求解过程。每个⼦问题的求解过程都构成⼀个「阶段」，在完成前⼀阶段的求解后才会进⾏后⼀阶段的求解。
2. **定义状态**：将和子问题相关的某些变量（位置、数量、体积、空间等等）作为一个「状态」表示出来。状态的选择要满⾜⽆后效性。
   - 一个「状态」对应一个或多个子问题，所谓某个「状态」下的值，指的就是这个「状态」所对应的子问题的解。
3. **状态转移**：根据「上一阶段的状态」和「该状态下所能做出的决策」，推导出「下一阶段的状态」。或者说根据相邻两个阶段各个状态之间的关系，确定决策，然后推导出状态间的相互转移方式（即「状态转移方程」）。
4. **初始条件和边界条件**：根据问题描述、状态定义和状态转移方程，确定初始条件和边界条件。
5. **最终结果**：确定问题的求解目标，然后按照一定顺序求解每一个阶段的问题。最后根据状态转移方程的递推结果，确定最终结果。

### 典型问题

**数塔问题**

[Problem - 1176](http://acm.hdu.edu.cn/showproblem.php?pid=1176)

构造树塔

![image-20251207201349164](https://chenalna.oss-cn-hangzhou.aliyuncs.com/img/image-20251207201349164.png)

n层，就有2^(n-1)条路径暴力算法

很多重复的计算

动态规划的话，复杂度（计算量）和结点数成正比

塔的数量和结点数成正比

结点数又和层数有关，n层节点有n^2/2.

先求小树塔，再往上求树塔。



**斐波那契问题**



子问题的解重复了，如果能搞定F（n-1）和F（n-2）就可以找到F（n）

分成已经上个月有的和上个月没有的，新出生的。

新出生的为什么等于F(n-2)？因为上上个月，无论是大还是小，到上个月（n-1）都是大兔了。

 $$f\left( n \right) =f\left( n-1 \right) +f\left( n-2 \right) $$

  动态规划的基本思路： 子问题的解重复了

如果我们能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，这样可以避免大量的重复计算，节省时间。我们用一个表来记录所有已解的子问题的答案。不管该子问题以后是否被用到，只要它被计算过，就将其结果填入表中。

  上述求斐波那契数列 的算法属于动态规划算法，其中数组dp（表）称为动态规划数组

动态规划也称为记录结果再利用的方法

求解斐波那契数列的递归算法理解动态规划算法

```
int count=1;//累计调用的步骤
int Fib(int n)
{printf("(%d)求解Fib(%d)\n",count++,n);
if (n==l || n==2)
{
printf("计算出Fib(%d)=%d\n",n,1);
return 1;
}

else{ 
int x=Fib(n-1);
int y=Fib(n-2);
printf("计算出Fib(%d)=Fib(%d)+Fib(%d)=%d\n",n, n-1, n-2, x+y);
return x+y;
}
}
```



 

 ![image-20260301163458548](https://chenalna.oss-cn-hangzhou.aliyuncs.com/img/image-20260301163458548.png)



为了避免重复计算，我们可以使用动态规划中的「表格处理方法」来处理。

这里我们使用「自底向上的递推方法」求解出子问题 
f(n-1)和 f(n-2)
 的解，然后把结果存储在表格中，供随后的计算查询使用。具体过程如下：

1. 定义一个数组 dp，用于记录斐波那契数列中的值。
2. 初始化 dp[0]=0,dp[1]=1。
3. 根据斐波那契数列的递推公式f(n)=f(n-1)+f(n-2) ，从dp(2) 开始递推计算斐波那契数列的每个数，直到计算出dp(n) 。
4. 最后返回 dp(n)即可得到第n项斐波那契数。


```
int dp[MAx];//所有元素初始化为0
int count=1;//累计调用的步骤
int Fib1(int n)//算法1
{dp[1]=dp[2]=1;
printf("(%d)计算出Fib(1)=1\n",count++);
printf("(%d)计算出Fib(2)=1\n",count++);
for (int i=3;i<=n;i++)
{ dp[i]=dp[i-1]+dp[i-2];
printf("(%d)计算出Fib1(%d)=%d\n",count++,i, dp[i]);
}
return dp[n];
```

这种使用缓存（哈希表、集合或数组）保存计算结果，从而避免子问题重复计算的方法，就是「动态规划算法」。

 ```mermaid
graph TD
	A[原问题] -->B[子问题1]
	A[原问题] -->C[子问题2]
	A[原问题] -->D[子问题n]
	B--> E[填表]
	C--> E[填表]
	D--> E[填表]
	E --> F[原问题的解]
 ```



 

 



![image-20260301164438317](https://chenalna.oss-cn-hangzhou.aliyuncs.com/img/image-20260301164438317.png)

![image-20260301164445073](https://chenalna.oss-cn-hangzhou.aliyuncs.com/img/image-20260301164445073.png)

动态规划问题的顺序解法

A->E对应的状态转移方程如下
$$
f(A)=0
f(S)=MIN_{存在<t,s>的有向边} \{f(t)+c(t,s)\}
$$


最长递增子序列问题

从左往右求，只要比前面大的+1；然后遍历一遍F数组，找最大的。

O(n^2)

可以优化

[Problem - 1160](http://acm.hdu.edu.cn/showproblem.php?pid=1160)

先按重量排序，然后找最长降序子序列

[Problem - 1087](http://acm.hdu.edu.cn/showproblem.php?pid=1087)

还是最长子序列

[Problem - 1421](http://acm.hdu.edu.cn/showproblem.php?pid=1421)

假设是递增序列

两个物品选一对搬一趟，疲劳度按原始相邻去搬

三个物品选一对搬一趟，比较谁比较接近。123、234来比。

min{(x1-x2)^2,(x2-x3)^2}

四个物品？

要么包含第四个物品，要么不包含

如果包含第四个物品，(x3-x4)^2

 如果不包含，从前三个选一对，重叠子问题。

动态就在于这个min

那么N个物品，看是否包含N了，即

F（N,1）=min{F(N-1),(x_n-1^2-x_n^2)+F(N-2,1)}



搬两趟

F(4,2)=x1-x2^2+x3-x4^2

F(5,2)=min{F(4,2),x_5-x_4^2+F(3,2)}

[Problem - 1058](http://acm.hdu.edu.cn/showproblem.php?pid=1058)



 F(n)=min{k1\*2,k2\*3,k3\*5,k4\*7}

递推公式——状态转移方程



**最长公共子序列（LCS）问题** 

[例5-2】求解最长公共子序列问题。给定两个序列A和B，称序列Z是A和B的公共子序列，是指Z同是A和的子序列。

该问题是求两序列A和B的最长公共子序列(LCS).

问题求解:若设$A=(a0，a1,....a_{m-1})，B=(b0，b1,....b_{n-1})，设Z=(z0，z1,z2，....z_{k-1})$为它们的最长公共子序列。不难证明有以下性质:

如果$a_{m-1}=b_{n-1}$, 则$z_{k-1}=a_{m-1}=b_{n-1}$,且$(z0,Z1 ....Z_{k-2})是(ao,a1, ...a_{m-2})和(bo，b1，....b_{n-2})$的一个最长公共子序列。

如果$a_{m-1}≠b{n-1}且z_{k-1}≠a_{m-1}$,则$(z0，Z1....Z_{k-1})是(ao，a1,....a_{m-2})和(bo,b1，....b_{n-1})$的一个最长公共子序列。

如果$a_{m-1}≠b_{n-1}且z_{k-1}≠b_{n-1}$,则$(z0,Z1,....Z_{k-1})是(ao,a1, ...a_{m-1})和(bo，b1，....b_{n-2})$的一个最长公共子序列。

定义二维动态规划数组dp，其中dp\[i][j]为子序列$(ao，a1，....a_{i-1})和(bo,b1....b_{j-1})$的最长公共子序列的长度。每考虑一个字符a[i]或b[j]都为动态规划的一个阶段(共经历约mxn个阶段)。

 

 dp[i\][j]为子序列(ao,a1,....ak-1)和(bo,b1,....bj-1)的最长公共子序列的长度。对应的状态转移方程如下:

> dp[i]\[j]=0 i=0或j=0边界条件
>
> dp[i]\[j]=dp[i-1]\[j-1]+1 	a[i-1]=b[j-1]
>
> dp[i]\[j]=MAX(dp[i]\[j-1],dp[i-1]\[j])	a[i-1]≠b[j-1]
>
> 显然，dp[m]\[n]为最终结果。

 

$$
\\
\left\{ \begin{array}{c}
	\text{其他情况，}a\left[ i-1 \right] \left( i-- \right) orb\left[ j-1 \right] \left( j-- \right) \text{是}LCS\text{一个字符} k--:\text{表示求的字符少}1\text{个}\\
	\begin{array}{l}
	if\,\,dp\left[ i \right] \left[ j \right] ==dp\left[ i-1 \right] \left( i-- \right) \,\,\left[ j \right] \left( \text{上方} \right)&		a\left[ i-1 \right] orb\left[ j-1 \right] \text{不是}LCS\text{中的字符}\\
	if\,\,dp\left[ i \right] \left[ j \right] ==dp\left[ i \right] \left[ j-1 \right] \left( j-- \right) \left( \text{左边} \right)&		a\left[ i-1 \right] orb\left[ j-1 \right] \text{不是}LCS\text{中的字符}\\
\end{array}\\
\end{array} \right. 
\\
$$






 ```
void LCSlength()//求dp

{ int i,j;
for (i=0;i<=m;i++)//将dp[i][0]置为0，边界条件
	dp[i][0]=0;
for (j=0;j<=n;j++)
	dp[0][j]=0;//将dp[0][j]置为0，边界条件
for (i=l;i<=m;i++) //mxn
for (j=1;j<=n;j++)//两重for循环处理a、b的所有字符
{ if (a[i-1]==b[j-1])//情况(1)
dp[i][j]=dp[i-1][j-1]+1;
	else//情况(2)
dp[i][j]=max(dp[i][j-1], dp[i-1][j]);
}
 ```



 ```
void Buildsubs()//由dp构造从subs
{ int k=dp[m][n];//k为a和b的最长公共子序列长度
int i=m;
int j=n;
while (k>0)//在subs中放入最长公共子序列(反向)
if (dp[i][j]==dp[i-1][j])
i--;
else if (dp[i][j]==dp[i][j-1])
j--;
else//与上方、左边元素值均不相等
{ subs.push_back(a[i-1]); //subs中添加a[i-1]
i--; j--; k--;}
}
 ```



  

#### 装配线调度问题

一工厂里有两条装配线并行生成汽车，line 1 and line 2

每条装配线有n个装配站$S_{i,1}...S_{i,n}\ ,i=1,2$

设对于每个$j,S_{1,j}和S_{2,j}$的功能相同，但装配时间不同，对$S_{i,j}$的装配时间为$a_{i,j}$,

汽车装配可以从一条装配线移到另一条装配线，从装配站$S_{i,j}$移到到另一条装配线上的时间为$t_{i,j} \ ,i=1,2 and j=1,2, ...,n-1$

汽车进入装配线的时间为ei;，汽车离开装配线的时间为xi

 

 

步骤二：



设$f_{i}[j]$表示一个汽车从起点到装配站$S_{i,j}$装配的最快可能时间。

递归公式:

$$
f_1 [j]=\left \{ \begin{array}{lr} 
	e_1 +a_{1,1}, & j=1 \\
	min(f_1[j-1]+a_{1,j}\ ,f_2 [j-1] +t_{2,j-1} +a_{1,j}) & j \ge2\\
\end{array} \right.
$$

$$
f_2 [j]=\left \{ \begin{array}{lr} 
	e_2 +a_{2,1}, & j=1 \\
	min(f_2[j-1]+a_{2,j}\ ,f_1 [j-1] +t_{1,j-1} +a_{2,j}) & j \ge2\\
\end{array} \right.
$$


总的时间

$f^*=min(f_1[n]+x_1,f_2[n]+x_2)$ 

与分治不同，它是一个迭代的过程，并非递归的过程

迭代从尾开始还是从头开始？从头开始！

#### 矩阵连乘问题

给定n个矩阵(A1,A2,...,An)

其中Ai与Ai+1(i=1,2...n-1)是可乘的。

用加括号的方法表示矩阵连乘的次序，不同加括号的方法所对应的计算次序是不同的。

找出一种最优的计算次序，使得n个矩阵元素相乘的次数最小

关键信息:有n个矩阵;任意相邻两个矩阵可以相乘;不考虑不相邻矩阵的乘法;加括号表示矩阵连乘的次序;括号一直加到最里层只剩2个矩阵相乘;找出n个矩阵相乘的次数最小的次序

有A1(3\*4),A2(4\*2),A3(2\*3),求以下相乘次序的矩阵连乘次数:

A1A2矩阵相乘次数=A1的行数\*A1的列数\*A2的列数=A1的行数\*A2的行数\*A2的列数

$A1(A2A3)\ \  A2A3=4*2*3=24次 \ \  A2A3(4*3) \ \ A1(A2A3)=3*4*3=36次\ \ A1(A2A3)=24+36=60次 \\ (A1A2)A3 \ \ A1A2=3*4*2=24次 \ \ A1A2(3*2) \ \  (A1A2)A3=3*2*3=18次\ \ (A1A2)A3=24+18=42次$

 

1个矩阵连乘有多少种划分方式

A1 0种

2个矩阵连乘有多少种划分方式

A1A2 1种

3个矩阵连乘有多少种划分方式

A1A2A3 2种

4个矩阵连乘有多少种划分方式



A1|A2A3A4 --> A1(A2A3A4)	-->A1(2种)  -->0种(2种）--> 2种

A1A2|A3A4 --> (A1A2)(A3A4) --> 1种

A1A2A3 |A4 --> (A1A2A3) A4 -- > (2种)A4 --> (2种)0(种) -->2种

> 设A(pi*qi),k为最佳分割的位置//pi行qi;列的i号矩阵(1≤i≤n)
>
> 设n个矩阵连乘的最佳计算次序为(A1A2...Ak)(Ak+1Ak+2...An),
>
> 则(A,A2...Ak)连乘的计算次序一定是最优的
>
> (Ak+1Ak+2...An)连乘的计算次序也一定是最优的。
>
> 反证法:假设(A1,A2...Ak)连乘的计算次序不是最优的,
>
> 或(Ak+1Ak+2...An)连乘的计算次序不是最优的。
>
> 令a:(A1,A2...Ak)连乘的乘法次数
>
> b:(Ak+1Ak+2...An)连乘的乘法次数
>
> C:(A1A2...Ak)(Ak+1Ak+2...An)连乘的乘法次数
>
> 则c=a+b
>
> 由于a不是最小的次数或b不是最小的次数，
>
> 则c肯定不是最小的次数，
>
> (A1,A2...Ak)(Ak+1Ak+2...An)不是最优决策,矛盾,故假设不真，





最优子结构

1. 缺啥补啥

2. 复述一遍最优子结构的定义:

   前提:有总体最优

   结论:有局部最优

3. 用反证法

   质疑结论:假设局部不是最优

4. 写质疑的过程

5. 证明矛盾

   指出矛盾,说明质疑失效

   肯定结论:局部是最优

   > 

![image-20260301165205198](https://chenalna.oss-cn-hangzhou.aliyuncs.com/img/image-20260301165205198.png)

若i<j,由Step1中的最优解结构可知:

假定最优括号化的分裂点为$k(i≤k≤j-1)$，则:

$m[i,j]=m[i,k]+m[k+1,j]+P_{i-1}P_kP_j$;

其中m[i,k]:子积$A_{i..k}$的最小代价，

$P_{i-1}:A_i$的行,$P_k:A_k$的列，$P_j:A_j$,的列

在不知道k的取值的情况下，可在j-i个值中选取最优者，所以$A_{i,j}$的最小计算成本为:

$$m[i,j] =
\begin{cases}
0 & i = j \\[6pt]
\displaystyle \min_{i \le k < j} \{ m[i,k] + m[k+1,j] + p_{i-1} p_k p_j \big\} & i < j
\end{cases}$$

若要构造最优解，定义S[i]\[j]记录分裂点k

 

#### 钢条切割

给定一根长度为 n 英寸的钢条和一个价格表 pi ，其中 i=1,2,…,n ，求切割方案，使得总销售价格 rn 最大。如果 pn 足够大，最优解可能不需要切割钢条。

Pi表示长度为i英寸钢条的直接售价

- 比如 p2=5 表示：如果直接卖一根 2 英寸的钢条，价格是 5 元。

 

rn表示长度为n的钢条通过最优切割（或不切割）能获得的最大收益

 

假设将钢条切成 k 段， 1≤k≤n ，各段长度分别为 ii,i2,…,ik ，有 n=ii+i2+⋯+ik ，总价格 rn=pii+pi2+⋯+pik 。

一般地，对于 rn ，其中 n≥1 ，可以转化为求更短的钢条切割问题最优解的和。

(14.1)rn=max{pn,r1+rn−1,r2+rn−2,…,rn−1+r1}

1、不切割，直接出售长度为n的钢条，价格为pn

2、切割
 ri+rn-i​：切割为 i 和 n−i两部分，并分别用它们的最优收益求和。
 最终取最大值即为 rn 的最优解。

 

为什么这么计算？

钢条切割具有最优子结构性质：问题的最优解可以通过子问题的最优解组合得到。

完成首次切割后，我们将问题转化为两个规模更小的子问题，并在所有肯能的两段切割方案中选择总价格最大的，构成原问题的最优解。我们称钢条切割问题满足**最优子结构(optimal substructure)**：问题的最优解由相关子问题的最优解组合而成，并且这些子问题能够独立求解。

除上述方法为，还有一种比较相似但更简单的递归方法，从钢条上切下长度为 i 的一段，且这段不再分割，对剩下的长度为 n−i 进行递归求解。

$r_n=max\{1≤i≤n_{pi}+r_{n−i}\}$此方法中，原问题的最优解只包含一个相关子问题的解。

 

#### 0-1背包问题

定义：

**背包问题是线性 DP 问题中一类经典而又特殊的模型。背包问题可以描述为：给定一组物品，每种物品都有自己的重量、价格以及数量。再给定一个最多能装重量为 W 的背包。现在选择将一些物品放入背包中，请问在总重量不超过背包载重上限的情况下，能装入背包的最大价值总和是多少？**

根据物品限制条件的不同，背包问题可分为：0-1 背包问题、完全背包问题、多重背包问题、二维费用背包、分组背包问题，以及混合背包问题、有依赖的背包等。

1.有背包

2.物品的价值/费用

DP问题中“状态”概念的理解

背包的每个可能容量就是“状态”，选择每个物品就是“咋状态的决策”

价值是你得到的，费用是你消耗的

**问题描述**

有N件物品和一个容量为V的背包。第i件物品的费用/重量是w[i],价值是v[i]。

- **背包容量**：W=5
- **物品列表**（每个物品只能选或不选）：即0-1背包问题

| **物品编号** | **重量 wi\*wi** | **价值 vi\*vi** |
| ------------ | --------------- | --------------- |
| 1            | 2               | 12              |
| 2            | 1               | 10              |
| 3            | 3               | 20              |
| 4            | 2               | 15              |

**目标**：在不超过背包容量的情况下，选择物品使总价值最大。

**定义**：**dp\[i][w]表示 前i个物品(物品0到物品i-1,一共i个物品.事实上也可以表示成物品1到物品i），背包容量为 w 时的最大价值**

每种物品有且仅有1件，可以选择不放入背包，也可以选择放入背包。

DP 的 i 表示的是物品的数量，不是编号。

1. 划分阶段

按照物品的序号、当前背包的载重上限进行阶段划分。

2. 定义状态

定义状态 dp\[i][w] 表示为：前 i 件物品放入一个最多能装重量为 w 的背包中（也并不一定会装满），可以获得的最大价值。

状态 dp\[i][w] 是一个二维数组，其中第一维代表「当前正在考虑的物品」，第二维表示「当前背包的载重上限」，二维数组值表示「可以获得的最大价值」。

3. 状态转移方程

对于「将前 i 件物品放入一个最多能装重量为 w 的背包中，可以获得的最大价值 」这个子问题，如果我们只考虑第 i-1件物品（前 i 件物品中最后一件物品）的放入策略（放入背包和不放入背包两种策略）。则问题可以转换为一个只跟前 i−1 件物品相关的问题。

1. **第 i-1 件物品不放入背包**：问题转换为「前 i−1 件物品放入一个最多能装重量为 w 的背包中 ，可以获得的最大价值」为 dp\[i−1][w]。

1. **第 i-1 件物品放入背包**：问题转换为「前 i−1 件物品放入一个最多能装重量为 w−weight[i−1] 的背包中(因为放入，因此是w减去这个物体的重量！剩余可用容量)，可以获得的最大价值」为 dp\[i−1][w−weight[i−1]]，再加上「放入的第 i−1 件物品的价值」为 value[i−1]，则此时可以获得的最大价值为 dp\[i−1][w−weight[i−1]]+value[i−1]。

​	意思是先占据了第i个物品对应的weight[i-1]这个重量大小，再去考虑前i-1个物品。但是包含这个物品好不好呢？所以取max。

既然第 i 件物品已经确定放进去了，那么：

- 它的价值已经拿到了
- 它的重量已经占用了

剩下的问题变成：

> 用 **前 i−1 件物品**
> 去填满 **剩余容量 w−weight[i−1]**

提问：为什么有的是

前i件物品要么包含第i个物品要么不包含。

如果没有第i个，只能从前i-1个物品选dp\[i][w]=dp\[i-1][w]

如果包含第i个，我还可以从前面选物品。dp\[i][w]=dp\[i-1][w-weight[i]]+value[i]

为什么谈的是第i-1个？

这个没必要去区分，第dp\[i][w]永远都是前i个物品。那么说考虑第i个，那么是1-i。考虑第i-1个，是0-i-1。

于是，前者不可能出现考虑第0个而是第1个，而后面可以是第0个，都是对于dp\[1][w]的考察。

为什么是weight[i]和value[i]?

那么你就把weight[0]和value[0]给忽略掉不就好了？

原来是0-i-1,对应 前i个物品

现在是 1-i对应前i个物品

dp[i] 一定表示“用了 i 个物品”

dp 的 i = 物品数量

把物品线性化，把物品排成一列，不需要排序的。先考虑第一个，在考虑第2个，在考虑前三个。具有包含的关系。如果这样就可以利用小问题的解，来解大问题。即动态规划

接下来我们再来考虑一下第 i-1件物品满足什么条件时才能考虑是否放入背包，并且在什么条件下一定不能放入背包。

1. 如果当前背包的载重不足时（即 w<weight[i−1]）:第 i -1件物品一定不能放入背包，此时背包的价值 dp\[i][w] 仍为 dp\[i−1][w] 时的价值，即 dp\[i][w]=dp\[i−1][w]。
2. 如果当前背包的载重足够时（即 w≥weight[i−1]）:第 i -1件物品可以考虑放入背包，或者不放入背包，此时背包的价值取两种情况下的最大值，即 dp\[i][w]=max{dp\[i−1][w],dp\[i−1][w−weight[i−1]]+value[i−1]}。

则状态转移方程为：



$$dp\left[ i \right] \left[ w \right] \left\{ \begin{array}{c}
	dp\left[ i-1 \right] \left[ w \right] ,w<weight\left[ i-1 \right]\\
	\max \left\{ dp\left[ i-1 \right] \left[ w \right] ,dp\left[ i-1 \right] \left[ w-weight\left[ i-1 \right] \right] +value\left[ i-1 \right] \right\} ,w\ge weight\left[ i-1 \right]\\
\end{array} \right. $$

4. 初始条件

- **如果背包载重上限为 0，则无论选取什么物品，可以获得的最大价值一定是 0，即 dp\[i][0]=0,0≤i≤size。**
- **无论背包载重上限是多少，前 0 件物品所能获得的最大价值一定为 0，即 dp\[0][w]=0,0≤w≤W。**

5. 最终结果

根据我们之前定义的状态，dp\[i][w] 表示为：前 i 件物品放入一个最多能装重量为 w 的背包中，可以获得的最大价值。则最终结果为 dp\[size][W]，其中 size 为物品的件数，W 为背包的载重上限

```python
class Solution:
    # 思路 1：动态规划 + 二维基本思路
    def zeroOnePackMethod1(self, weight: [int], value: [int], W: int):
        size = len(weight)
        dp = [[0 for _ in range(W + 1)] for _ in range(size + 1)]
        # 枚举前 i 种物品
        for i in range(1, size + 1):
            # 枚举背包装载重量
            for w in range(W + 1):
                # 第 i - 1 件物品装不下
                if w < weight[i - 1]:
                    # dp[i][w] 取「前 i - 1 件物品装入载重为 w 的背包中的最大价值」
                    dp[i][w] = dp[i - 1][w]
                else:
                    # dp[i][w] 取「前 i - 1 件物品装入载重为 w 的背包中的最大价值」与「前 i - 1 件物品装入载重为 w - weight[i - 1] 的背包中，再装入第 i - 1 物品所得的最大价值」两者中的最大值
                    dp[i][w] = max(dp[i - 1][w], dp[i - 1][w - weight[i - 1]] + value[i - 1])
                    
        return dp[size][W]
    
    
    后面这个部分也可以改成
               # 枚举第 i - 1 组物品能取个数
         for w in range(W + 1):
                dp[i][w] = dp[i - 1][w]
                for k in range(group_count[i - 1]):
                    if w >= weight[i - 1][k]:
                        # dp[i][w] 取所有 dp[i - 1][w - weight[i - 1][k]] + value[i - 1][k] 中最大值
                        dp[i][w] = max(dp[i][w], dp[i - 1][w - weight[i - 1][k]] + value[i - 1][k])
```

![image-20260303014707264](https://chenalna.oss-cn-hangzhou.aliyuncs.com/img/image-20260303014707264.png)

(价值，体积)

大问题分解成小问题，递推有，动态规划也有。

复杂度分析:O(nxW),n为物品数量，W为背包的载重上限。二维数组嘛。

每个格子运算量为常量。因此时间复杂度仍为nxW

时间复杂度：O（nxW).

背包问题滚动数组

状态转移的过程中，只用到了当前行(第i行)以及上一行(第i-1行)

并且最后得到的结果只要(5,1)对应的10

没必要保存所有阶段的状态。只需要保存上一阶段的所有状态和当前阶段的所有状态。

用两个一维数组分别保存相邻两个阶段的所有状态。dp\[0][w]保存原先dp\[i-1][w]，用dp\[1][w]保存当前dp\[1][w]的状态。

或者更进一步，只需要用一个一维数组dp\[w]保存上一阶段所有状态，采用滚动数组的方式对空间进行优化。

变成一维的

| (V,C) | 0    | 1    | 2    | 3    | 4    | 5    | 6    | 7    | 8    | 9    | 10   |
| ----- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- |
| 0     | 0    | 0    | 0    | 0    | 0    | 1    | 1    | 1    | 1    | 1    | 2    |

为什么？因为dp\[1][10]=dp\[1][5]+value[1]=2,而原来是dp\[0][5]=0,而只有一件物品。

前面这个值就是用当前这个物品得到的，而之前是上一行上个物品得到的。

那就不用这个物品，确保是上一趟的物品。

运算的时候从后往前走。这样就不会用到当前物品的结果了。

1. 划分阶段

按照物品的序号、当前背包的载重上限进行阶段划分。

2. 定义状态

定义状态 dp[w] 表示为：物品放入一个最多能装重量为 w 的背包中（也并不一定会装满），可以获得的最大价值。

3. 状态转移方程

$$dp\left[ w \right] =\begin{cases}
	dp\left[ w \right]&		w<weight\left[ i-1 \right]\\
	\max \left\{ dp\left[ w \right] ,dp\left[ w-weight\left[ i-1 \right] \right] +value\left[ i-1 \right] \right\}&		w\ge weight\left[ i-1 \right]\\
\end{cases}$$

最终结果为dp[W]

伪代码:

```
class Solution:
    # 思路 2：动态规划 + 滚动数组优化
    def zeroOnePackMethod2(self, weight: [int], value: [int], W: int):
        size = len(weight)
        dp = [0 for _ in range(W + 1)]
        
        # 枚举前 i 种物品
        for i in range(1, size + 1):
            # 逆序枚举背包装载重量（避免状态值错误）
            for w in range(W, weight[i - 1] - 1, -1):
                # dp[w] 取「前 i - 1 件物品装入载重为 w 的背包中的最大价值」与「前 i - 1 件物品装入载重为 w - weight[i - 1] 的背包中，再装入第 i - 1 物品所得的最大价值」两者中的最大值
                dp[w] = max(dp[w], dp[w - weight[i - 1]] + value[i - 1])
                
        return dp[W]
//若是for w in range(W,-1,-1),那么需要判断。w与weight[i-1] 


```

空间成功优化到一维

二维写法本质是：

```
当前行 = 上一行+ 允许选择当前物品带来的提升
```

而一维写法其实就是：

```
直接在同一数组上完成这个过程
```



分数背包问题

背包携带的最大重量不超过W，求解目标:在不超过负重的前提下，使装入的总价值最大，与0/1背包的问题是，每个物品可以取一部分装入背包。

贪心策略：有3种可供选择

1. 价值最大
2. 重量轻
3. 选择单位重量价值最大的物品

每次选择单位重量价值最大的物品，如果其重量小于背包容量，就装入，并将容量减去该物品的重量，然后就面临了一个最优子问题。

```
class Solution:
    def fractionalKnapsack(self, weight: [int], value: [int], W: int):
        """
        分数背包问题 - 贪心算法解法
        :param weight: 物品重量列表
        :param value: 物品价值列表
        :param W: 背包最大承重
        :return: 背包能装的最大总价值
        """
        size = len(weight)
        
        # 计算每个物品的单位重量价值，并创建物品列表
        items = []
        for i in range(size):
            # 单位重量价值 = 价值 / 重量
            unit_value = value[i] / weight[i]
            items.append({
                'weight': weight[i],
                'value': value[i],
                'unit_value': unit_value,
                'index': i
            })
        
        # 按照单位重量价值降序排序
        items.sort(key=lambda x: x['unit_value'], reverse=True)
        
        total_value = 0  # 总价值
        remaining_weight = W  # 剩余容量

        # 贪心选择
        for item in items:
            if remaining_weight <= 0:
                break
                
            if item['weight'] <= remaining_weight:
                # 可以完整装入整个物品
                total_value += item['value']
                remaining_weight -= item['weight']
            
            else:
                # 只能装入物品的一部分
                fraction = remaining_weight / item['weight']
                part_value = item['value'] * fraction
                total_value += part_value

                remaining_weight = 0
                
        return total_value
    
```

**关键区别**：

- 分数背包：**只看眼前**，做出选择后不再回头
- 0/1背包：需要考虑**所有可能性**，选择最优组合

**贪心选择性质体现**：

- 每次都选择**当前单位价值最高**的物品
- 不考虑未来可能更好的选择
- **局部最优选择** → 能装就装，不能装就装部分



完全背包:一种物品可以取无数个

增加一层循环，转化为[0-1]背包问题

很简单，假设每个物品有总重/物体重w/weight[i]，比如2kg物品A，10kg容量，那么5个A物品



状态转移方程

选择0件第i-1件物品：dp\[i-1][w]

选择1件第i-1件物品：dp\[i-1][w-weight[i-1]]+value[i-1]

...

选择k件第i-1件物品:dp\[i-1][w-kxweight[i-1]]+kxvalue[i-1]

> 注意：选择k件第i-1件物品的条件是0≤kxweight[i-1]≤w



状态转移方程为:$dp[i][w]=max\{dp[i-1][w-k\times weight[i-1]]+k\times value[i-1]\},0\leq k\times weight[i-1] \leq w$

```python
class Solution:
    # 思路 1：动态规划 + 二维基本思路
    def completePackMethod1(self, weight: [int], value: [int], W: int):
        size = len(weight)
        dp = [[0 for _ in range(W + 1)] for _ in range(size + 1)]
        
        # 枚举前 i 种物品
        for i in range(1, size + 1):
            # 枚举背包装载重量
            for w in range(W + 1):
                # 枚举第 i - 1 种物品能取个数
                for k in range(w // weight[i - 1] + 1):
                    # dp[i][w] 取所有 dp[i - 1][w - k * weight[i - 1] + k * value[i - 1] 中最大值
                    dp[i][w] = max(dp[i-1][w], dp[i - 1][w - k * weight[i - 1]] + k * value[i - 1])
            dp[i][w] = max( dp[i - 1][w - k * weight[i - 1]] + k * value[i - 1])
        return dp[size][W]
    
    
   class Solution:
    # 思路 3：动态规划 + 滚动数组优化
    def completePackMethod3(self, weight: [int], value: [int], W: int):
        size = len(weight)
        dp = [0 for _ in range(W + 1)]
        
        # 枚举前 i 种物品
        for i in range(1, size + 1):
            # 正序枚举背包装载重量
            for w in range(weight[i - 1], W + 1):
                # dp[w] 取「前 i - 1 种物品装入载重为 w 的背包中的最大价值」与「前 i 种物品装入载重为 w - weight[i - 1] 的背包中，再装入 1 件第 i - 1 种物品所得的最大价值」两者中的最大值
                dp[w] = max(dp[w], dp[w - weight[i - 1]] + value[i - 1])
                
        return dp[W]
//若是for w in range(W,-1,-1),那么需要判断。w与weight[i-1]  
```

$$
dp[i][w] = \max \left\{
\begin{array}{c}
dp[i-1][w] \\
dp[i-1][w - weight[i-1]] + value[i-1] \\
dp[i-1][w - 2 \times weight[i-1]] + 2 \times value[i-1], \\
\ldots \\
dp[i-1][w - k \times weight[i-1]] + k \times value[i-1]
\end{array}
\; \Bigg| \; 0 \le k \times weight[i-1] \le w
\right.
$$

令 $w = w - weight[i-1]$，有 $dp[i][w - weight[i-1]]$：

$$
dp[i][w - weight[i-1]] = \max \left\{
\begin{array}{c}
dp[i-1][w - weight[i-1]] \\
dp[i-1][w - 2 \times weight[i-1]] + value[i-1] \\
dp[i-1][w - 3 \times weight[i-1]] + 2 \times value[i-1] \\
\ldots \\
dp[i-1][w - k \times weight[i-1]] + (k-1) \times value[i-1] \\
dp[i-1][w - (k+1) \times weight[i-1]] + k \times value[i-1]
\end{array}
\; \Bigg| \; 0 \le k \times weight[i-1] \le w - weight[i-1]
\right.
$$

令 $k = k-1$：

$$
dp[i][w - weight[i-1]] = \max \left\{
\begin{array}{c}
dp[i-1][w - weight[i-1]] \\
dp[i-1][w - 2 \times weight[i-1]] + value[i-1] \\
dp[i-1][w - 3 \times weight[i-1]] + 2 \times value[i-1] \\
\ldots \\
dp[i-1][w - k \times weight[i-1]] + (k-1) \times value[i-1]
\end{array}
\; \Bigg| \; weight[i-1] \le k \times weight[i-1] \le w
\right.
$$

因此：

$$
dp[i][w] = \max \left\{ dp[i-1][w], \; dp[i][w - weight[i-1]] + value[i-1] \right\}, \quad w \ge weight[i-1]
$$

最终得到递推式：

$$
dp[i][w] = 
\begin{cases}
dp[i-1][w], & w < weight[i-1] \\[4pt]
\max \left\{ dp[i-1][w], \; dp[i][w - weight[i-1]] + value[i-1] \right\}, & w \ge weight[i-1]
\end{cases}
$$


因为原本我们需要遍历所有 k（件数）来求 max，但现在我们只需要在递推时先计算dp\[i][w-weight[i-1]]（它已经自动 max 了所有 k≥1 情形），



这个思路背后的思想是 **"最优子结构的最优子结构"**，或者更具体地说，是 **"利用同层状态的自嵌套来消除枚举"**。

```
dp[i][w] 中取多件的最优值 
= dp[i][w - weight[i-1]] + value[i-1]
```

原始思路：

- 要决定取 k 件物品 i，需要枚举所有 k
- 新思路：**取 k 件 = 取 1 件 + 已经考虑过取 k-1 件的状态**

```
取 k 件的最优值 = (取 1 件的价值) + (在剩余容量中取 k-1 件的最优值)
```



而这个"在剩余容量中取 k-1 件的最优值"，**正好就是 dp\[i][w - weight[i-1]]**！

因为 dp\[i][w - weight[i-1]] 已经递归地包含了"再取一件"的所有可能性。

这就像：

```
要到达第 k 级台阶 = 先到达第 k-1 级台阶 + 再走一级
```

当你决定取一件物品 i 后，剩下要解决的问题是：
"在容量 w - weight[i-1] 中，继续取物品 i（以及前面的物品）的最优值"

**这个子问题完全等同于原问题！** 只是容量变小了。

伪代码

```python
class Solution:
    # 思路 2：动态规划 + 状态转移方程优化
    def completePackMethod2(self, weight: [int], value: [int], W: int):
        size = len(weight)
        dp = [[0 for _ in range(W + 1)] for _ in range(size + 1)]
        
        # 枚举前 i 种物品
        for i in range(1, size + 1):
            # 枚举背包装载重量
            for w in range(W + 1):
                # 第 i - 1 件物品装不下
                if w < weight[i - 1]:
                    # dp[i][w] 取「前 i - 1 种物品装入载重为 w 的背包中的最大价值」
                    dp[i][w] = dp[i - 1][w]
                else:
                    # dp[i][w] 取「前 i - 1 种物品装入载重为 w 的背包中的最大价值」与「前 i 种物品装入载重为 w - weight[i - 1] 的背包中，再装入 1 件第 i - 1 种物品所得的最大价值」两者中的最大值
                    dp[i][w] = max(dp[i - 1][w], dp[i][w - weight[i - 1]] + value[i - 1])
                    
        return dp[size][W]
```

如果要求背包必须装满，该怎么处理？

难道要先按照0-1背包的思路，然后再把情况按价值从高到低，排除装不满的。第一个装满的就是答案。

对于不考虑物品，当背包体积是1的时候 ，没有装满啊，那就是-1，代表无解

所以dp\[1][6]也是-1



1. 只有载重上限为0的背包，在不放入物品时，能够恰好装满背包（有合法解），此时背包所含物品的最大价值为0 ，即dp[0]=0 。
2. 其他载重上限下的背包，在放入物品的时，都不能恰好装满背包（都没有合法解），此时背包所含物品的最大价值属于未定义状态，值应为 $-\infty，即dp[w]=-\infty,0 \le w\le W$ 。



```python
class Solution:
    # 0-1 背包问题 求恰好装满背包的最大价值
    def zeroOnePackJustFillUp(self, weight: [int], value: [int], W: int):
        size = len(weight)
        dp = [float('-inf') for _ in range(W + 1)]
        dp[0] = 0
        
        # 枚举前 i 种物品
        for i in range(1, size + 1):
            # 逆序枚举背包装载重量（避免状态值错误）
            for w in range(W, weight[i - 1] - 1, -1):
                # dp[w] 取「前 i - 1 件物品装入载重为 w 的背包中的最大价值」与「前 i - 1 件物品装入载重为 w - weight[i - 1] 的背包中，再装入第 i - 1 物品所得的最大价值」两者中的最大值
                dp[w] = max(dp[w], dp[w - weight[i - 1]] + value[i - 1])
        
        if dp[W] == float('-inf'):
            return -1
        return dp[W]
```

多重背包

**多重背包问题**：有n种物品和一个最多能装重量为W 的背包，第 i种物品的重量为 weight[i]，价值为value[i] ，件数为count[i] 。请问在总重量不超过背包载重上限的情况下，能装入背包的最大价值是多少？

转换成0-1背包

对于容量为w的背包，最多可以装$min\{count[i-1],\frac{w}{weight[i-1]}\}$

$dp[i][w]=max{dp[i-1][w-k\times weight[i-1]]+k\times value[i-1]},0\le k \le min\{count[i-1],\frac{w}{weight[i-1]}\}$

伪代码

```python
class Solution:
    # 思路 1：动态规划 + 二维基本思路
    def multiplePackMethod1(self, weight: [int], value: [int], count: [int], W: int):
        size = len(weight)
        dp = [[0 for _ in range(W + 1)] for _ in range(size + 1)]
        
        # 枚举前 i 种物品
        for i in range(1, size + 1):
            # 枚举背包装载重量
            for w in range(W + 1):
                # 枚举第 i - 1 种物品能取个数
                for k in range(min(count[i - 1], w // weight[i - 1]) + 1):
                    # dp[i][w] 取所有 dp[i - 1][w - k * weight[i - 1] + k * value[i - 1] 中最大值
                    dp[i][w] = max(dp[i][w], dp[i - 1][w - k * weight[i - 1]] + k * value[i - 1])
                    
        return dp[size][W]

   
    
    同理的滚动数组
      for k in range(min(count[i - 1], w // weight[i - 1]) + 1):
                    # dp[w] 取所有 dp[w - k * weight[i - 1]] + k * value[i - 1] 中最大值
                    dp[w] = max(dp[w], dp[w - k * weight[i - 1]] + k * value[i - 1])
```

$$\text{而在「多重背包问题」中，我们在递推}dp\left[ i \right] \left[ w \right] \text{时，是无法从}dp\left[ i \right] \left[ w-weight\left[ i-1 \right] \right] \text{状态得知目前究竟已经使用了多个件第}\left[ i-1 \right] \text{种物品，也就无法判断第}\left[ i-1 \right] \text{种物品是否还有剩余数量可选。这就导致了我们无法通过优化「状态转移方程」的方式将「多重背包问题」的时间复杂度降低。}$$

**完全背包**：不需要记录件数 → 可以同层转移。

**多重背包**：需要知道目前用了多少件 → 同层转移无法获取这个信息，因为数组只存最大价值，不存件数。

举一反三、触类旁通啊

用少量的物品来替代原来的大量物品

从物品数量入手，通过「二进制优化」的方式，将算法的时间复杂度降低。从物品数量入手，通过「二进制优化」的方式，将算法的时间复杂度降低。

简单来说，就是把物品的数量count[i]拆分成由$1,2,4...,2^m$件单个物品组成的大物品，以及剩余不足2的整数次幂数量的物品，由$$count\left[ i \right] -\left( 2^{\lfloor \log _{2}^{\left( count\left[ i \right] +1 \right)} \rfloor}-1 \right) $$件单个物品组成的大物品

伪代码

```python
class Solution:
    # 思路 3：动态规划 + 二进制优化
    def multiplePackMethod3(self, weight: [int], value: [int], count: [int], W: int):
        weight_new, value_new = [], []
        
        # 二进制优化
        for i in range(len(weight)):
            cnt = count[i]//这个物品的数量
            k = 1
            while k <= cnt:
                cnt -= k
                weight_new.append(weight[i] * k)
                value_new.append(value[i] * k)
                k *= 2
            if cnt > 0:
                weight_new.append(weight[i] * cnt)
                value_new.append(value[i] * cnt)
        
        dp = [0 for _ in range(W + 1)]
        size = len(weight_new)
        
        # 枚举前 i 种物品
        for i in range(1, size + 1):
            # 逆序枚举背包装载重量（避免状态值错误）
            for w in range(W, weight_new[i - 1] - 1, -1):
                # dp[w] 取「前 i - 1 件物品装入载重为 w 的背包中的最大价值」与「前 i - 1 件物品装入载重为 w - weight_new[i - 1] 的背包中，再装入第 i - 1 物品所得的最大价值」两者中的最大值
                dp[w] = max(dp[w], dp[w - weight_new[i - 1]] + value_new[i - 1])
                    
        return dp[W]
```

混合背包问题

> **混合背包问题**：有n 种物品和一个最多能装重量为 W的背包，第 i种物品的重量为 weight[i]，价值为value[i] ，件数为count[i] 。其中：
>
> 1. 当 count[i]=-1时，代表该物品只有1 件。
> 2. 当count[i]=0 时，代表该物品有无限件。
> 3. 当 count[i]>0时，代表该物品有count[i] 件。
>
> 请问在总重量不超过背包载重上限的情况下，能装入背包的最大价值是多少？



并且在「多重背包问题」中，我们曾经使用「二进制优化」的方式，将「多重背包问题」转换为「0-1 背包问题」，那么在解决「混合背包问题」时，我们也可以先将「多重背包问题」转换为「0-1 背包问题」，然后直接再区分是「0-1 背包问题」还是「完全背包问题」就可以了。



```python
class Solution:
    def mixedPackMethod1(self, weight: [int], value: [int], count: [int], W: int):
        weight_new, value_new, count_new = [], [], []
        
        # 二进制优化
        for i in range(len(weight)):
            cnt = count[i]
            # 多重背包问题，转为 0-1 背包问题
            if cnt > 0:
                k = 1
                while k <= cnt:
                    cnt -= k
                    weight_new.append(weight[i] * k)
                    value_new.append(value[i] * k)
                    count_new.append(1)
                    k *= 2
                if cnt > 0:
                    weight_new.append(weight[i] * cnt)
                    value_new.append(value[i] * cnt)
                    count_new.append(1)
            # 0-1 背包问题，直接添加
            elif cnt == -1:
                weight_new.append(weight[i])
                value_new.append(value[i])
                count_new.append(1)
            # 完全背包问题，标记并添加
            else:
                weight_new.append(weight[i])
                value_new.append(value[i])
                count_new.append(0)
                
        dp = [0 for _ in range(W + 1)]
        size = len(weight_new)
    
        # 枚举前 i 种物品
        for i in range(1, size + 1):
            # 0-1 背包问题
            if count_new[i - 1] == 1:
                # 逆序枚举背包装载重量（避免状态值错误）
                for w in range(W, weight_new[i - 1] - 1, -1):
                    # dp[w] 取「前 i - 1 件物品装入载重为 w 的背包中的最大价值」与「前 i - 1 件物品装入载重为 w - weight_new[i - 1] 的背包中，再装入第 i - 1 物品所得的最大价值」两者中的最大值
                    dp[w] = max(dp[w], dp[w - weight_new[i - 1]] + value_new[i - 1])
            # 完全背包问题
            else:
                # 正序枚举背包装载重量
                for w in range(weight_new[i - 1], W + 1):
                    # dp[w] 取「前 i - 1 种物品装入载重为 w 的背包中的最大价值」与「前 i 种物品装入载重为 w - weight[i - 1] 的背包中，再装入 1 件第 i - 1 种物品所得的最大价值」两者中的最大值
                    dp[w] = max(dp[w], dp[w - weight_new[i - 1]] + value_new[i - 1])
                    
        return dp[W]
```



分组背包



>**分组背包问题**：有n组物品和一个最多能装重量为W 的背包，第 i组物品的件数为group_count[i] ，第 i组的第j 个物品重量为weight\[i][j] ，价值为value\[i][j] 。每组物品中最多只能选择 1件物品装入背包。请问在总重量不超过背包载重上限的情况下，能装入背包的最大价值是多少？



1. 按照物品种类的序号，当前背包的载重上限进行阶段划分

2. 定义状态

​	定义状态dp\[i][w]表示为： 前i组物品放入一个最多能装重量为w的背包中，可以获得的最大价值。

状态dp\[i][w]是一个二维数组，其中第一维代表「当前正在考虑的物品组数」，第二维表示「当前背包的载重上限」，二维数组值表示「可以获得的最大价值」。



由于我们可以不选择第i-1组物品中的任何物品，也可以从第i-1组物品的0-group_count[i-1]-1件物品中随意选择1件物品，所以状态dp\[i][w]可能从以下方案选择最大值。

状态转移方程：

$dp[i][w]=max\{dp[i-1][w],dp[i-1][w-weight[i-1][k]]+value[i-1][k]\},0\le k \le group_count[i-1] $



代码

```python
class Solution:
    # 思路 1：动态规划 + 二维基本思路
    def groupPackMethod1(self, group_count: [int], weight: [[int]], value: [[int]], W: int):
        size = len(group_count)
        dp = [[0 for _ in range(W + 1)] for _ in range(size + 1)]
        
        # 枚举前 i 组物品
        for i in range(1, size + 1):
            # 枚举背包装载重量
            for w in range(W + 1):
                # 枚举第 i - 1 组物品能取个数
                dp[i][w] = dp[i - 1][w]
                for k in range(group_count[i - 1]):
                    if w >= weight[i - 1][k]:
                        # dp[i][w] 取所有 dp[i - 1][w - weight[i - 1][k]] + value[i - 1][k] 中最大值
                        dp[i][w] = max(dp[i][w], dp[i - 1][w - weight[i - 1][k]] + value[i - 1][k])
```

滚动数组

```python
class Solution:
    # 思路 2：动态规划 + 滚动数组优化
    def groupPackMethod2(self, group_count: [int], weight: [[int]], value: [[int]], W: int):
        size = len(group_count)
        dp = [0 for _ in range(W + 1)]
        
        # 枚举前 i 组物品
        for i in range(1, size + 1):
            # 逆序枚举背包装载重量
            for w in range(W, -1, -1):
                # 枚举第 i - 1 组物品能取个数
                for k in range(group_count[i - 1]):
                    if w >= weight[i - 1][k]:
                        # dp[w] 取所有 dp[w - weight[i - 1][k]] + value[i - 1][k] 中最大值
                        dp[w] = max(dp[w], dp[w - weight[i - 1][k]] + value[i - 1][k])
                        
        return dp[W]
```

二维费用背包

> **二维费用背包问题**：有n件物品和有一个最多能装重量为W 、容量为V 的背包。第 i件物品的重量为 weight[i]，体积为volumn[i] ，价值为value[i] ，每件物品有且只有 1件。请问在总重量不超过背包载重上限、容量上限的情况下，能装入背包的最大价值是多少？

不管是容量还是称重还是其它，对于我们来说都是cost花费

定义状态

$dp[i][w][v]$:前i件物品放入一个最多能装w、容量为v的背包中，可以获得的最大价值.最终结果为dp\[size]][W]\[V]



$dp[i][w][v]=max{dp[i-1][w][v],dp[i-1][w-weight[i-1]][v-volumn[i-1]]+value[i-1]},0 \le weight[i-1] \le w,0 \le volum $



> 注意：采用这种「状态定义」和「状态转移方程」，往往会导致内存超出要求限制，所以一般我们会采用「滚动数组」对算法的空间复杂度进行优化。



```python
class Solution:
    # 思路 1：动态规划 + 三维基本思路
    def twoDCostPackMethod1(self, weight: [int], volume: [int], value: [int], W: int, V: int):
        size = len(weight)
        dp = [[[0 for _ in range(V + 1)] for _ in range(W + 1)] for _ in range(size + 1)]
    
        # 枚举前 i 组物品
        for i in range(1, N + 1):
            # 枚举背包装载重量
            for w in range(W + 1):
                # 枚举背包装载容量
                for v in range(V + 1):
                    # 第 i - 1 件物品装不下
                    if w < weight[i - 1] or v < volume[i - 1]:
                        # dp[i][w][v] 取「前 i - 1 件物品装入装载重量为 w、装载容量为 v 的背包中的最大价值」
                        dp[i][w][v] = dp[i - 1][w][v]
                    else:
                        # dp[i][w][v] 取所有 dp[w - weight[i - 1]][v - volume[i - 1]] + value[i - 1] 中最大值
                        dp[i][w][v] = max(dp[i - 1][w][v], dp[i - 1][w - weight[i - 1]][v - volume[i - 1]] + value[i - 1])
                        
        return dp[size][W][V]
    
    
    class Solution:        
    # 思路 2：动态规划 + 滚动数组优化
    def twoDCostPackMethod2(self, weight: [int], volume: [int], value: [int], W: int, V: int):
        size = len(weight)
        dp = [[0 for _ in range(V + 1)] for _ in range(W + 1)]
        
        # 枚举前 i 组物品
        for i in range(1, N + 1):
            # 逆序枚举背包装载重量
            for w in range(W, weight[i - 1] - 1, -1):
                # 逆序枚举背包装载容量
                for v in range(V, volume[i - 1] - 1, -1):
                    # dp[w][v] 取所有 dp[w - weight[i - 1]][v - volume[i - 1]] + value[i - 1] 中最大值
                    dp[w][v] = max(dp[w][v], dp[w - weight[i - 1]][v - volume[i - 1]] + value[i - 1])
                    
        return dp[W][V]

```

滚动数组优化：

dp[w]\[v]表示：将物品装入最多能重量为w、容量为v的背包中，可以获得的最大值。

状态转移方程

$dp[w][v]=max\{dp[w][v],dp[w-weight[i-1]][v-volume[i-1]]+value[i-1]\},0 \le weight[i-1] \le w ,0 \le volume[i-1] \le v$

最终结果为$dp[W][V]$

求方案总数

依赖背包