本蒟蒻的第...额，忘了第多少篇了题解

这次写的是01背包，题目传送门、

简单的概括下题目，在N个有价值（v[i]）有重量(w[i])东西里头，尽可能拿价值最多的。

那么，定义一个二维数组f[i][j],i表示到第i个东西时，j表示还可以装最多j重量的东西，f[i][j]表示此时的总价值。那么对于f[i][j]而言，就只有取和不取两种情况

1.不取，则f[i][j]=f[i][j] 2.取,则f[i][j]=f[i-1][j-w[i]]+v[i](表示剩余重量减少，价值增加)

这里便是精髓，就是对比1和2哪个更大，也就是哪个的价值更多 可以用max函数 即f[i][j]=max(f[i][j],f[i-1][j-w[i]]+v[i]);

剩下的不用讲，输入和输出 本题是个模板题哦！

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