题解 | 【模板】完全背包

#include<bits/stdc++.h>
using namespace std;
const int N=1e3+10;

int T;
int n,m,w[N],v[N],dp[N]; 

void solve(){
	memset(dp,0,sizeof(dp));
	
	for(int i=1;i<=n;i++){
		for(int j=w[i];j<=m;j++){
			dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
		}
	}
	
	cout<<dp[m]<<endl;
	return;
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	cin>>T;
	while(T--){
		cin>>n>>m;
		for(int i=1;i<=n;i++){
			cin>>w[i]>>v[i];
		}
		solve();
	}

    return 0;
}