DP初步:状态转移与递推
最少硬币问题
- 有多个不同面值的硬币(任意面值)
- 数量不限
- 输入金额S,输出最少硬币组合。
回顾用贪心求解硬币问题
硬币面值1、2、5。支付13元,要求硬币数量最少
贪心:
(1)5元硬币,2个
(2)2元硬币,1个
(3)1元硬币,1个
硬币面值1、2、4、5、6.,支付9元。
贪心:
(1)6元硬币,1个
(2)2元硬币,1个
(3)1元硬币,1个
错误!
答案是:5元硬币+4元硬币=2个
硬币问题的正解是动态规划
type = [1,5,10,25,50]
5种面值
定义数组Min[]
,记录最少硬币数量:
对输入的某个金额i,Min[i]
是最少的硬币数量
第一步,只考虑1元面值的硬币
金额i: 0,1,2,3,4,5
硬币数量`Min[]`:0,1,2,3,4
- i=1元时,等价于:i = i - 1 = 0 元需要的硬币数量,加上1个1元硬币
- i=2元时,等价于:i = i - 1 = 1 元需要的硬币数量,加上1个1元硬币
- …
在1元硬币的计算结果基础上,再考虑加上5元硬币的情况,从i=5开始就行了
i=5元时,等价于
- i = i - 5 = 0元需要的硬币数量,加上1个5元硬币,
Min[5] = 1
- 原来的
Min[5] = 5
取1和2的最小值,所以Min[5] = 1
i = 6元时,等价于 - i = i - 5 = 1元需要的硬币数量,加上1个5元硬币,
Min[6] = 2
- 原来的
Min[6] = 6
取1和2的最小值,所以Min[6] = 2
Min[6] = Min[5] + 1
递推关系:
Min[i] = min (Min[i], Min[i - 5] + 1)
继续处理其它面值硬币
#include <iostream>
#include <vector>
#include <limits.h>
using namespace std;
void solve(int s)
{
int cnt = 5; //5种硬币
vector<int> type = {1,5,10,25,50}; //5种面值
vector<int> Min(s+1, INT_MAX); //初始化为无穷大
Min[0] = 0;
for (int j = 0; j < cnt; j ++) //5种硬币
{
Min[i] = min (Min[i], Min[i - type[j]] + 1);
}
cout << Min[s] << endl;
}
int main()
{
int s;
cin >> s;
solve(s);
return 0;
}
DP的两个特征
- 重叠子问题
在递归算法中,尤其是在解决最优化问题时,经常会遇到这样的情况:在求解大问题的过程中,我们需要多次求解规模更小、结构相同的问题。这些小问题被称为子问题。如果这些子问题在大问题求解过程中被重复计算多次,这将导致算法效率低下,因为大量时间被重复的子问题求解所占据。动态规划通过存储子问题的解(通常在二维数组中,称为DP表),确保每个子问题只计算一次,从而避免了重复计算。当需要某个子问题的解时,直接从DP表中查找,如果该子问题尚未解决,则先解决它,然后存储其解。 - 最优子结构
这是动态规划能够成功解决许多问题的另一个关键特性。最优子结构是指一个问题的最优解包含其子问题的最优解。换句话说,如果我们能找到所有子问题的最优解,那么我们可以通过这些子问题的最优解来构建原问题的最优解。动态规划利用这个性质,通过自底向上的方式(即先解决最基础的子问题,然后逐步解决更大规模的子问题)来构建问题的最优解。
DP:记忆化
如果各个子问题不是独立的,如果能够保存已经解决的子问题的答案,在需要的时候再找出已求得的答案,可以避免大量的重复计算。
基本思路:用一个表记录所有已解决的子问题的答案,不管该问题以后是否被用到,只要它被计算过,就将其结果填入表中。
记忆化
解题步骤
- 拆分问题
- 定义状态(并找出初状态)
- 状态转移方程
一般的模型方法 - 递归搜索法
- 记忆化搜索(记忆化暴力)
- 递推式法
最经典的DP问题:0/1背包
给定n种物品和一个背包,物品i的重量是 w i w_{i} wi其价值为 v i v_{i} vi,背包的容量为C.
背包问题:选择装入背包的物品,使得装入背包中物品的总价值最大
如果在选择装入背包的物品时,对每种物品i只有两种选择:装入背包或不装入背包,称为0/1耆包问题,
与装载问题不同的是,0/1背包不能只装一部分,要么选,要么不选。
设 x i x_{i} xi表示物品i装入背包的情况
x i x_{i} xi=0,表示物品i没有被装入背包
x i x_{i} xi=1,表示物品i被装入背包
约束条件:
∑ i = 1 n w i x i ≤ C x i ∈ { 0 , 1 } ( 1 ≤ i ≤ n ) \begin{array}{} \sum_{i=1}^{n}w_{i}x_{i} \le C \\ x_{i}\in \left \{ 0,1 \right \}(1 \le i \le n) \end{array} ∑i=1nwixi≤Cxi∈{0,1}(1≤i≤n)
目标函数:
m a x ∑ i = 1 n v i x i max\sum_{i=1}^{n}v_{i}x_{i} maxi=1∑nvixi
例:有5个物品,重量分别是{2,2,6,5,4},价值分别为{6,3,5,4,6},背包容量为10
定义一个(n+1)(C+1)
的二维表dp[][]
dp[i][j]
表示把前i个物品装入背包中花费容量为j的情况下获得的最大价值
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | |
---|---|---|---|---|---|---|---|---|---|---|---|
0 | |||||||||||
1 | |||||||||||
2 | |||||||||||
3 | |||||||||||
4 | |||||||||||
5 | |||||||||||
填表,按只放第一个物品,只放前2个,只放前3个…一直到放完,这样的顺序考虑(从小问题扩展到大问题) |
- 只装第一个物品(横向是递增的背包容量)
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | |
---|---|---|---|---|---|---|---|---|---|---|---|
0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
1 | 0 | 0 | 6 | 6 | 6 | 6 | 6 | 6 | 6 | 6 | 6 |
2 | |||||||||||
3 | |||||||||||
4 | |||||||||||
5 |
- 只装前2个物品
如果第2个物品重量比背包容量大,那么不能装第2个物品,情况和只装第1个一样
如果第2个物品重量小于背包容量,那么- 如果把物品2装进去(重量是2),那么相当于只把1装到(容量-2)的背包中
- 如果不装2,那么相当于只把1装到背包中
- 取1和2的最大值
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | |
---|---|---|---|---|---|---|---|---|---|---|---|
0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
1 | 0 | 0 | 6 | 6 | 6 | 6 | 6 | 6 | 6 | 6 | 6 |
2 | 0 | 0 | 6 | 6 | 9 | 9 | 9 | 9 | 9 | 9 | 9 |
3 | |||||||||||
4 | |||||||||||
5 |
- 只装前3个物品
如果第3个物品重量比背包大,那么不能装第3个物品,情况和只装第1、2个一样。
如果第3个物品重量小于背包容量,那么- 如果把物品3装进去(重量是6),那么相当于只把1、2装到(容量-6)的背包中
- 如果不装3,那么相当于只把1、2装到背包中
- 取1和2的最大值
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | |
---|---|---|---|---|---|---|---|---|---|---|---|
0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
1 | 0 | 0 | 6 | 6 | 6 | 6 | 6 | 6 | 6 | 6 | 6 |
2 | 0 | 0 | 6 | 6 | 9 | 9 | 9 | 9 | 9 | 9 | 9 |
3 | 0 | 0 | 6 | 6 | 9 | 9 | 9 | 9 | 11 | 11 | 14 |
4 | |||||||||||
5 |
按这样的规律一行行填表,直到结束,现在回头考虑,装了那些物品,看最后一列,15>14,说明装了物品5,否则价值不会变化
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | |
---|---|---|---|---|---|---|---|---|---|---|---|
0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
1 | 0 | 0 | 6 | 6 | 6 | 6 | 6 | 6 | 6 | 6 | 6 |
2 | 0 | 0 | 6 | 6 | 9 | 9 | 9 | 9 | 9 | 9 | 9 |
3 | 0 | 0 | 6 | 6 | 9 | 9 | 9 | 9 | 11 | 11 | 14 |
4 | 0 | 0 | 6 | 6 | 9 | 9 | 9 | 10 | 11 | 13 | 14 |
5 | 0 | 0 | 6 | 6 | 9 | 9 | 12 | 12 | 15 | 15 | 15 |
小明的背包1
【题目描述】小明有一个容量为C的背包。这天他去商场购物,商场一共有N件物品,第i件物品的体积为 c i c_{i} ci,价值为 w i w_{i} wi。小明想知道在购买的物品总体积不超过C的情况下所能获得的最大价值为多少,请你帮他算算。
【输入描述】输入第1行包含两个正整数 N,C,表示商场物品的数量和小明的背包容量。
第 2~N+1 行包含 2个正整数c,w,表示物品的体积和价值。 1 ≤ N ≤ 1 0 2 1 \le N\le 10^2 1≤N≤102, 1 ≤ C ≤ 1 0 3 1 \le C\le 10^3 1≤C≤103, 1 ≤ w i , c i ≤ 1 0 3 1 \le w_{i},c_{i}\le 10^3 1≤wi,ci≤103
【输出描述】输出一行整数表示小明所能获得的最大价值。
DP状态设计
DP状态:定义二维数组dp[][]
,大小为NxC
dp[i][j]
:把前i个物品(从第1个到第i个)装入容量为j的背包中获得的最大价值。
把每个dp[i][j]
看成一个背包:背包容量为j,装1~i这些物品。最后得到的dp[N][C]
就是问题的答案:把N个物品装进容量c的背包的最大价值。
DP状态转移方程
递推计算到dp[i][j]
分2种情况:
- 第i个物品的体积比容量j还大,不能装进容量j的背包。那么直接继承前i-1个物品装进容量j的背包的情况即可:
dp[i][j]= dp[i-1][j]
- 第i个物品的体积比容量j小,能装进背包。又可以分为2种情况:装或者不装第i个,
- 装第i个,从前i-1个物品的情况下推广而来,前i-1个物品是
dp[i-1][j]
。第i个物品装进背包后,背包容量减少c[i]
,价值增加w[i]
。有:dp[i][j]= dp[i-1][j-c[i]] + w[i]
。 - 不装第i个,那么:
dp[i][j] = dp[i-1][j]
- 取1和2的最大值
状态转移方程
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - c[i]] + w[i])
- 装第i个,从前i-1个物品的情况下推广而来,前i-1个物品是
代码
#include <bits/stdc++.h>
using namespace std;
const int N = 3011;
int w[N], c[N]; //物品的价值和体积
int dp[N][N];
int solve (int n, int C)
{
for (int i = 1; i <= n; i++)
{
for (int j = 0; j <= C; j++)
{
if (C[i]>j) //第i个物品比背包还大,装不了
dp[i][j] = dp[i-1][j];
else //第i个物品可以装
dp[i][j] = max(dp[i-1][j], dp[i-1][j-c[i]] + w[i]);
}
}
return dp[n][C];
}
int main()
{
int n, C;
cin >> n >> C;
for (int i = 1; i <= n; i++)
{
cin >> c[i] >> w[i];
}
memset(dp, 0, sizeof(dp)); //清0
cout << solve(n, C);
return 0;
}
空间优化:滚动数组
把dp[][]
优化成一维的dp[]
,以节省空间。
Dp[i][]
是从上面一行dp[i-1]
算出来的,第i行只跟第i-1行有关系,跟更前面的行没有关系!
dp[i][j]=max(dp[i-1][j],dp[i-1][j- c[i]]+ w[i])
优化:只需要两行dp[0][]
、dp[1][]
,用新的一行覆盖原来的一行,交替滚动。
经过优化,空间复杂度从O(NxC)减少为O©。
定义dp[2][j]
:用dp[0][]
和dp[1][]
交替滚动。
优点:逻辑清晰、编码不易出错,建议初学者采用这个方法
因为我们新一行的计算只与上一行有关所以,两行重复使用即可
伪代码:
int w[N], c[N]; //物品的价值和体积
int dp[2][N]; //替换int dp[][];
solve (int n, int C)
{
now = 0, old = 1; //now指向当前正在计算的一行,old指向旧的一行
for (int i = 1; i <= n; i ++)
{
//交替滚动,now始终指向最新的一行
if(c[i] > j)
dp[now][j] = dp[old][j];
else
dp[now][j] = max(dp[old][j], dp[old][j - c[i]] + w[i]);
}
return dp[now][C]; //返回最新的行
}
自我滚动
因为状态转移每次只与上一层有关,所以用一个一维数组就可以。
继续精简:用一个一维的dp[]
就够了,自己滚动自己。
dp[j]=dp[j-c[i]]+w[i]
为什么从大到小遍历,看dp[j]=dp[j-c[i]]+w[i]
这一状态转移,是根据小的改大的,如果先把小的改了那小的还会被用到,数据就不对了,所以从大到小
for (int i = 0; i < n; i ++) //遍历每一件物品
{
//遍历背包容量,表示在上一层的基础上,容量为j时,第i件物品装或不装的最优解
for (int j = C; j >= c[i]; j --)
{
dp[j] = max(dp[j-c[i]] + w[i], dp[j]);
}
}
j从小往大循环是错误的
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | |
---|---|---|---|---|---|---|---|---|---|---|
dp[j]' |
0 | 0 | 6 | 6 | 6 | 6 | 6 | 6 | 6 | 6 |
dp[j] |
0 | 0 | 6 | 6 | 6 | 9 | 6 | 6 | 6 | 6 |
例如i=2时,上图的dp[5]
经计算得到dp[5]=9
,把dp[5]
更新为9。
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | |
---|---|---|---|---|---|---|---|---|---|---|
dp[j]' |
0 | 0 | 6 | 6 | 6 | 9 | 6 | 6 | 6 | 6 |
dp[j] |
0 | 0 | 6 | 6 | 6 | 9 | 6 | 6 | 12 | 6 |
下图中继续往后计算,当计算dp[8]时
,得dp[8]=dp[5]'+3=9+3=12
这个答案是错的。
错误的产生是滚动数组重复使用同一个空间引起的.
j从大到小循环是对的
例如i = 2时,首先计算最后的dp[9] = 9
,它不影响前面状态的计算
1.
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | |
---|---|---|---|---|---|---|---|---|---|---|
dp[j]' |
0 | 0 | 6 | 6 | 6 | 6 | 6 | 6 | 6 | 6 |
dp[j] |
0 | 0 | 6 | 6 | 6 | 6 | 6 | 6 | 6 | 9 |
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | |
---|---|---|---|---|---|---|---|---|---|---|
dp[j]' |
0 | 0 | 6 | 6 | 6 | 6 | 6 | 6 | 6 | 9 |
dp[j] |
0 | 0 | 6 | 6 | 6 | 6 | 6 | 6 | 9 | 9 |
初始化细节
装满 dp[0]=0
,其余赋值-INF;
不装满全初始化为 0;
若一定要求装满:
则必有n=sum(c[i])
, i ∈ i \in i∈已选集合
所以dp[n-sum(c[i])]= dp[0]
所以只有从dp[0]
出发才合法,那就把其他的设成无穷小。
//装满
memset (dp, -0x3f, sizeof(dp));
dp[0] = 0;
//不装满
memset (dp, 0, sizeof(dp));