文章摘要

GPT 4

此内容根据文章生成，并经过人工审核，仅用于文章内容的解释与总结

动态规划DP

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

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

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

背包DP

01背包

例题：01背包

有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。

第 i 件物品的体积是 vi ，价值是 wi 。

求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。输出最大价值。

输入格式

第一行两个整数，N，V ，用空格隔开，分别表示物品数量和背包容积。

接下来有 N 行，每行两个整数 vi,wi ，用空格隔开，分别表示第 i 件物品的体积和价值。

输出格式

输出一个整数，表示最大价值。

输入样例

输出样例：

0<N,V≤1000

0<vi,wi≤1000

解法：贪心（不可取），DFS，DP

贪心

使用贪心法完全取决于输入的数据，不可能完全正确。

DFS搜索每种取物方案。代价O(n^2)

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; 
}

只有放和不放两种选择。

不放：f[i][j]=f[i-1][j]

放：f[i][j]=f[i-1][j-w[i]]+v[i]

所以转移方程为f[i][j]=max(f[i-1][j],f[i-1][j-w[i]]+v[i])

示例代码是模版！！！

#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空间复杂度优化

实际上，由状态转移方程和dp二维数组的值很容易发现：

  |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])

更多习题

洛谷P1060，P1048，P1164

完全背包

例题：完全背包

有 N 种物品和一个容量是 V 的背包，每种物品都有无限件可用。

第 i 种物品的体积是 vi ，价值是 wi 。

求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。输出最大价值。

输入格式

第一行两个整数，N，V ，用空格隔开，分别表示物品种数和背包容积。

接下来有 N 行，每行两个整数 vi,wi ，用空格隔开，分别表示第 i 种物品的体积和价值。

输出格式

输出一个整数，表示最大价值。

输入样例

输出样例：

0<N,V≤1000

0<vi,wi≤1000

使用和01背包一样的方式

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

示例代码是模版！！！

#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

优化

将原始算法的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])