01背包（枚举及动态规划）

下面的01背包代码使用了深度优先搜索（DFS）来实现背包的求解，这种方式的好处是代码较简单且容易理解，但对于一些较大的数据，则会导致算法运行缓慢（因为需要枚举所有情况）
时间复杂度O(2ⁿ)

#include<bits/stdc++.h>
using namespace std;
int m,n;// m表示背包容量，n表示物品数量
int w[22],c[22]; // w数组存储每个物品的重量，c数组存储每个物品的价值
int maxx;// 用于记录能获得的最大价值
void dfs(int step,int W,int C){
	if(step>=n+1){ // 当已经考虑完所有物品
		if(W<=m&&C>maxx)maxx=C;
		return;
	}
	dfs(step+1,W,C); // 不选择当前物品
	dfs(step+1,W+w[step],C+c[step]);// 选择当前物品
}
int main(){
	cin>>m>>n;
	for(int i=1;i<=n;i++){
		cin>>w[i]>>c[i];
	} 
	dfs(1,0,0);
	cout<<maxx;
	return 0; 
}

因此，在这种情况下，可以使用动态规划进行代码优化
优化后的时间复杂度为O(n²)

#include<bits/stdc++.h>
using namespace std;
int m,n; // m表示背包容量，n表示物品数量
int w[25],c[25]; // w数组用于存储物品的重量，c数组用于存储物品的价值
int maxx=-1;//写完才发现根本没用上
int dp[205][205]; // 二维动态规划数组，dp[i][j]表示在前i个物品中，背包容量为j时能获得的最大价值
int main(){
	cin>>m>>n;
	for(int i=1;i<=n;i++){
		cin>>w[i]>>c[i];
	}
	for(int i=1;i<=n;i++){	//外层循环便利物品
		for(int j=1;j<=m;j++){	//便利背包容量
			if(j-w[i]>=0)
				dp[i][j]=max(dp[i-1][j-w[i]]+c[i],dp[i-1][j]);	//如果可以放下
			else
				dp[i][j]=dp[i-1][j];	//如果放不下
		}
	}
	cout<<dp[n][m];
}