动态规划——背包问题

01背包问题：

定义：01背包顾名思义，就是数量要么就是0要么就是1不能重复取一件物品。动态规划是不断决策求最优解的过程，「0-1 背包」即是不断对第 i个物品的做出决策，「0-1」正好代表不选与选两种决定。

二维数组：（图片来自b站up主，新手不太懂这个思路的可以去看看up主的讲解）

思路：定义一个状态f[i][j]指在前i个物品，背包容量j下的最优解

1. 将初始状态f[0][0]置为0

2. 若 j<v[i] 时，表明容量不够，没法选，则为前i-1个物品的最优解，对应代码：f[i][j]=f[i-1][j]

3. 若 j>=v[i]时，表示容量充足我们可以选择这个物品，也可以不选这个物品

• 选择这个物品：f[i][j]=f[i-1][j-v[i]]+w[i]
• 不选择这个物品：f[i][j]=f[i-1][j]
• 最后决策通过取两个的最大值max()

参考代码：

#include<bits/stdc++.h>
using namespace std;
const int N=1010;
int v[N],w[N],f[N][N];//f存储状态 
int main(){
	int n,m;
	cin>>n>>m; 
	for(int i=1;i<=n;i++){
		cin>>v[i]>>w[i];
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			if(v[i]>j) f[i][j]=f[i-1][j];
			else f[i][j]=max(f[i-1][j],f[i-1][j-v[i]]+w[i]);
		}
	}
	cout<<f[n][m]<<endl;
	
	
	
	return 0;
} 

（更优化）一维数组：将状态f[i][j]优化到一维f[j]，实际上只需要做一个等价变形

思路：

1. 状态f[j]定义：N 件物品，背包容量 j 下的最优解

2. 枚举背包容量时从m开始

3. 为什么要逆序？

• 在二维情况下，状态f[i][j]是由上一轮i - 1的状态得来的，f[i][j]与f[i - 1][j]是独立的。而优化到一维后，如果我们还是正序，则有f[较小体积]更新到f[较大体积]，则有可能本应该用第i-1轮的状态却用的是第i轮的状态
• 例如，一维状态第i轮对体积为 3 的物品进行决策，则 f[7] 由 f[4] 更新而来，这里的 f[4] 正确应该是 f[i - 1][4]，但从小到大枚举j这里的 f[4] 在第i轮计算却变成了 f[i][4] 。当逆序枚举背包容量j时，我们求f[7]同样由 f[4] 更新，但由于是逆序，这里的f[4]还没有在第i轮计算，所以此时实际计算的 f[4] 仍然是 f[i - 1][4] 。
• 简而言之：这里运用倒序是为了防止数据被污染
• 状态转移公式为：

参考代码：

#include<bits/stdc++.h>
using namespace std;
const int N=1010;
int f[N]; 
int main(){
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		int v,w;
		cin>>v>>w;
		for(int j=m;j>=v;j--){
		f[j]=max(f[j],f[j-v]+w);
		}
	}
	
	cout<<f[m]<<endl;
	
	
	return 0;
} 

完全背包问题：