01背包问题是动态规划问题的子背包问题，算是蓝桥杯以及CSP较为常考的一种题型。

这种问题是有一个板子的，非常简单

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

int k[200],v[200],dp[130][130];
int main() {
	int t,m;
	cin>>t>>m;
	for (int i=1;i<=m;i++){
		cin>>k[i]>>v[i];
	}
	for (int i=1;i<=m;i++){
		for (int j=0;j<=t;j++){
			if (k[i]>j)dp[i][j]=dp[i-1][j];
			else dp[i][j]=max(dp[i-1][j],dp[i-1][j-k[i]]+v[i]);
		}
	}
	cout<<dp[m][t];
	return 0;
}

但是如果我们遇到了t与m特别大特别大的情况的话，就会爆空间，直接jj，所以我们要优化空间复杂度，怎么办呢？用滚动数组！

所以优化后的板子又来了

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

int k[200],v[200],dp[13000];
int main() {
	int t,m;
	cin>>t>>m;
	for (int i=1;i<=m;i++){
		cin>>k[i]>>v[i];
	}
	for (int i=1;i<=m;i++){
		for (int j=0;j<=t;j++){
			if (k[i]<=j)dp[j]=max(dp[j],dp[j-k[i]]+v[i]);
		}
	}
	cout<<dp[t];
	return 0;
}

会了吗？会了的话就要使用，所以我们来看例题吧！

例题1

有一个容量为m(m<=20000)的背包，现在有n(n<=2000)个物品，体积为v[i],价值分别为w[i]，现要你装入一些物品，使得在体积小于等于m的情况下，价值尽可能大。

分析

典型的标准的01背包的模板题，所以直接用

例题2

P1048 [NOIP2005 普及组] 采药 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

分析

这道题与正常的01背包问题有点区别，这道题有病，那就是这道题没有排序，所以我们要在j的那个循环那里从t开始，这样就可以避免答案不正确的情况

例题3

有一个容量为m(m<=20000)的背包，现在有n(n<=2000)个物品，体积为v[i]，现要你装入一些物品使得体积和最大

分析

这道题就更简单了，直接在模板的基础上删除存储价值的数组，然后将所有的使用价值数组的地方改成体积数组就可以了

例题4

有一个容量为m(m<=20000)的背包，现在有n(n<=2000)个物品，体积为v[i],价值分别为w[i]，现要你装入一些物品，使得在体积恰好等于m的情况下，价值尽可能大，如果无法满足要求，输出“-1”。

分析

这道题有点考思路，咱们先用二维dp的思想来考虑一下，如果是0个物体放在空间为j的背包里，会有情况吗？不会啊，所以我们要把dp[0][j]的值全部都设成负无穷（INT_MIN）但是dp[0][0]不能设置成负无穷，因为0个物体放在空间为0的背包里是可以的。所以要将dp[0][0]设成0。

现在二维的我们想清楚了，就该考虑滚动数组的了，其实dp[0][0]设为0，就是在滚动数组里将dp[0]设为0，其余的都设成负无穷就可以了，灰常的简单。

看到这里你学废了吗你学会了吗，没学会再看一遍，如果还没学会就直接问我吧。

跪谢王大佬，陈厚节老师，杨老师提供思路

 看了这么久，作者也写了这么久，能不能点一个赞，在收藏一下呢？最好的话在点个关注吧

谢谢啦！