题解

#include<bits/stdc++.h>
using namespace std;
int main() {
	int  n,m;
	cin>>n>>m;
	vector<int> w(n+1),v(n+1);
	for(int i=1;i<=n;i++){
		cin>>w[i];
	}
	for(int i=1;i<=n;i++){
		cin>>v[i];
	}
	// dp[i][j] 处理第 i 个水晶，背包容量是 j 的时候，能够获得的最大价值
	vector<vector<int>> dp(n+1,vector<int>(m+1,0));
	//对于每个水晶进行判断
	for(int i=1;i<=n;i++){
		//第 i 个水晶在背包容量为 j 的时候，记录最大价值 
		for(int j=0;j<=m;j++){
			//此时背包容量无法装下这个物品
			//背包在 i-1 的时候 容量为 j 的最大值 
			if(w[i]>j) dp[i][j]=dp[i-1][j]; 
			//前一个不装入背包，剩余空间在 i-1 的时候
			//容量为 j-w[i] 的最大价值 价格自己的价值 
			else dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+v[i]);
		}
	} 
	cout<<dp[n][m]; 
	return 0;
}