题解

经典01背包

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

const int M = 110, T = 1e3 + 10;
int w[M], v[M]; 
int dp[T]; 

int main() {
	
	int t, m; 
	cin >> t >> m;
	for(int i = 1; i <= m; i++) {
		cin >> w[i] >> v[i];
	}
	for(int i = 1; i <= m; i++) { 
		for(int j = t; j >= w[i]; j--) { 
			dp[j] = max(dp[j], dp[j-w[i]] + v[i]);
		}
	}
	cout << dp[t]; 

	return 0;
}