[洛谷P1048]#采藥

題目連結

01背包裸題

直接上模闆

//背包裸題

#include <algorithm>
#include<iostream>
#include<cstdio>

using namespace std;

const int MAXM = 100+5;

int dp[MAXM + 1][MAXM + 1];
int main() {
	int T,M,v[MAXM],w[MAXM];
	cin >> T >> M;
	for (int i = 0; i < M; i++)
	{
		scanf("%d %d", &w[i], &v[i]);	//消耗時間即可看做為重量
	}
	//DP
	for (int i = M - 1; i >= 0; i--) {
		for (int j = 0; j <= T; j++) {
			if (j < w[i]) {
				dp[i][j] = dp[i + 1][j];
			}
			else {
				dp[i][j] = max( dp[i + 1][j],dp[i + 1][j - w[i]] + v[i] );
			}
		}
	}

	cout << dp[0][T] << endl;

}