A85.采药

01背包

#include <iostream>
using namespace std; 

const int maxT=1005, maxM=105;
int T, M;
int w[maxT], v[maxM];
int dp[maxM][maxT];

int main() {
	cin >> T >> M;
	for (int i=1; i<=M; i++) {
		cin >> w[i] >> v[i];
	}
	//01背包，初始化为0可以省略
	for (int i=1; i<=M; i++) {//枚举物品 
		for (int j=0; j<=T; j++) {//枚举背包容量
			if (j-w[i] >= 0) {//能装下第i个物品的时候判断是否装 
		 		dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]]+v[i]);
			} else {//装不下第i个物品就沿用之前的选择 
				dp[i][j] = dp[i-1][j];
			}
		}
	}
	cout << dp[M][T]; 
	return 0;
}