背包问题

01背包

 一般的动态规划要先考虑好状态，这个状态是一个集合，要能分成几个子集，然后从这些子集（小问题），推到这一整个集合（大问题），且求解过程是一样的，就可以可以转换成大问题分解成小问题一个一个求解，最后合并

先要知道状态表示什么

再要知道dp的属性，应该跟所求有关，只会有最大值，最小值，和数量的情况。

然后要知道你这个问题集合里，能从小问题推到大问题这个条件是什么（满足这个条件，才能推过来），还有是从哪些大问题，化解成的小问题

还有状态计算，也就是问题集合的划分，把每一种情况算出来，要求不重，不漏

有一些状态需要拐个弯才能求解，比如说含i，可以先求不含i，最后再补上i，是等价的

但是注意，有些集合划分出来的可能是空集，也就是不存在，就必须j<vi的时候，j-vi就不存在了，写代码的时候要注意一下

例题

[AcWing] 2. 01背包问题（C++实现）0-1背包问题模板题_c++0-1背包模版-CSDN博客

 二维

#include <bits/stdc++.h>
using namespace std;

const int N=1005;
int n, m, v[N], w[N], f[N][N];
int main() 
{
	scanf("%d%d", &n, &m);
	for (int i=1; i<=n; i++) scanf("%d%d", &v[i], &w[i]);
	
	//f[0][0~m]=0
	
	for (int i=1; i<=n; i++)
		for (int j=0; j<=m; j++)
		{
			f[i][j]=f[i-1][j];
			if (j>=v[i]) f[i][j]=max(f[i][j], f[i-1][j-v[i]]+w[i]);
		}
	
	printf("%d", f[n][m]);
	return 0;
}

一维写法（滚动优化）

由于第i件物品只跟第i-1件物品有关，每次都是这件跟前一件有关，所以先去掉一维

#include <bits/stdc++.h>
using namespace std;

const int N=1005;
int n, m, v[N], w[N], f[N];
int main() 
{
	scanf("%d%d", &n, &m);
	for (int i=1; i<=n; i++) scanf("%d%d", &v[i], &w[i]);
	
	//f[0][0~m]=0
	
	for (int i=1; i<=n; i++)
		for (int j=0; j<=m; j++)
		{
			f[j]=f[j]; //这里是没啥用的，可以删掉
			if (j>=v[i]) f[j]=max(f[j], f[j-v[i]]+w[i]); //删掉上一行之后，我们发现这里j可以直接从v[i]开始遍历
		}
	
	printf("%d", f[m]);
	return 0;
}

　　整理一下变成

#include <bits/stdc++.h>
using namespace std;

const int N=1005;
int n, m, v[N], w[N], f[N];
int main() 
{
	scanf("%d%d", &n, &m);
	for (int i=1; i<=n; i++) scanf("%d%d", &v[i], &w[i]);
	
	//f[0][0~m]=0
	
	for (int i=1; i<=n; i++)
		for (int j=v[i]; j<=m; j++)
			f[j]=max(f[j], f[j-v[i]]+w[i]);
		
	
	printf("%d", f[m]);
	return 0;
}

　　但是这样是不对的，关键在于j循环的顺序   举例证明的方法：AcWing 2. 01背包问题 - AcWing 

看完举例的方法之后，你就会发现，这句话等价与

f[i][j]=max(f[i][j], f[i][j-v[i]]+w[i]);

但是和原来不符，原因是从小打大循环时，会出现前面值被改的情况，但是从大到小就可以保证前面值不会改变

终极写法：

#include <bits/stdc++.h>
using namespace std;

const int N=1005;
int n, m, v[N], w[N], f[N];
int main() 
{
	scanf("%d%d", &n, &m);
	for (int i=1; i<=n; i++) scanf("%d%d", &v[i], &w[i]);
	
	//f[0][0~m]=0
	
	for (int i=1; i<=n; i++)
		for (int j=m; j>=v[i]; j--)
			f[j]=max(f[j], f[j-v[i]]+w[i]);
		
	
	printf("%d", f[m]);
	return 0;
}

完全背包