动态规划DP

• 参考资料：https://oi-wiki.org/dp/

动态规划是一种通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。

由于动态规划并不是某种具体的算法，而是一种解决特定问题的方法，因此它会出现在各式各样的数据结构中，与之相关的题目种类也更为繁杂。

在 OI 中，计数等非最优化问题的递推解法也常被不规范地称作 DP，因此本章将它们一并列出。事实上，动态规划与其它类型的递推的确有很多相似之处，学习时可以注意它们之间的异同。

背包DP

01背包

例题：01背包

1
2
3
4
5

4 5
1 2
2 4
3 4
4 5

1

8

1
2
3
4
5
6
7

int dfs(int now,int sumv){
	int res;
	if(now==n+1) return res=0;//没有了
	if(sumv<v[now]) res=def(now+1,sumv);//无法选第i个
	else res=max(dfs(now+1,sumv),dfs(now+1,sumv-v[now])+w[now]);
	return res; 
} 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

#include<bits/stdc++.h>
#define ll long long
using namespace std; 
ll n,m;
ll w[10001],v[10001];
ll f[1001][1001];
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>w[i]>>v[i];
	}
	for(int i=1;i<=n;i++){
		for(int j=m;j>=0;j--){
			if(j<w[i]) f[i][j]=f[i-1][j];
			else f[i][j]=max(f[i-1][j],f[i-1][j-w[i]]+v[i]);
		}
	}
	cout<<f[n][m];
	return 0;
}

01空间复杂度优化

• 参考资料：https_blog.csdn.net/?url=https%3A%2F%2Fblog.csdn.net%2Fsweeney_he%2Farticle%2Fdetails%2F119452077
  实际上，由状态转移方程和dp二维数组的值很容易发现：

1
2
3
4
5
6

  |1  2  3  4  5  6  7  8  9  10 11 12 13 14 15 16 17 18 19 20
——|————————————————————————————————————————————————————————————
1 |0  0  0  0  0  0  0  5  5  5  5  5  5  5  5  5  5  5  5  5
2 |0  0  0  0  0  0  0  5  6  6  6  6  6  6  6  6  11 11 11 11
3 |0  0  0  0  7  7  7  7  7  7  7  7  12 13 13 13 13 13 13 13
4 |0  3  3  3  7  7  10 10 10 10 10 10 12 13 15 16 16 16 16 16

第i行的数据只依赖于第i-1行的值，因此我们只需保存第i-1行和第i行这两行的值即可，即两个一维数组dp1[]和dp2[]

dp1[ j ] 等价于 dp[i-1] [ j ]

dp2[ j ] 等价于 dp[ i ] [ j ]

所以新的转移方程：dp2[j] = max(dp1[j-c[i]]+w[i],dp2[j])

完全背包

例题：完全背包

1
2
3
4
5

4 5
1 2
2 4
3 4
4 5

1

10

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

#include<iostream>
using namespace std;
const int N = 1010;
int n, m;
int dp[N];
int main(){
    cin >> n >> m;
    for(int i = 1; i <= n; i ++ ){
        int v, w;
        cin >> v >> w;
        for(int j = v; j <= m; j ++ ){
                dp[j] = max(dp[j], dp[j - v] + w);
        }
    }
    cout << dp[m] << endl;
}

完全背包优化

• 参考：https_blog.csdn.net/?url=https%3A%2F%2Fblog.csdn.net%2Fm0_51507437%2Farticle%2Fdetails%2F122782623

1. 优化

将原始算法的DP思想转变一下：

对于第i种物品的出现，我们对第i种物品放不放入背包进行决策。如果不放那么V(i,j)=V(i-1,j)；
如果确定放，背包中应该出现至少一件第i种物品，所以V(i,j)中至少应该出现一件第i种物品，即V(i,j)=V(i,j-wi)+vi。为什么会是V(i,j-wi)？因为V(i,j-wi)里面可能有第i种物品，也可能没有第i种物品。我们要确保V(i,j)至少有一件第i件物品，所以要预留wi的空间来存放一件第i种物品。
那么完全背包和 01 背包的不同点在哪里呢？

从二维数组上区别 01 背包和完全背包，也就是状态转移方程就差别在放第 i 种物品时，完全背包在选择放这个物品时，最优解是 V(i, j)=max｛V(i, j-kw(i))+kv(i)｝即同行的那一个，而 01 背包比较的是V(i,j)=max｛V(i-1,j)，V(i-1,j-w(i))+v(i)｝，上一行的那一个。

所以状态转移方程近似于01：

f[i][j]=max(f[i-1][j],f[i][j-c[i]]+w[i])

2. 降维

同01背包。

多重背包

备注

参考资料同文中内容。

版权所有©Minecraft-Sep