题解 | #采药#

#include<iostream>
using namespace std;

int dp[1001][101];
int w[101];
int v[101];

int main() {
	int n, m;
	while (cin >> n >> m) {
		for (int i = 0; i < m; i++) {
			cin >> w[i] >> v[i];
		}
		for (int i = 0; i <= n; i++) {
			dp[i][0] = 0;
		}
		for (int i = 0; i < m; i++) {
			dp[0][i] = 0;
		}
		// 考虑0-m-1个商品中的总价值最大
		for (int x = 1; x <= n; x++) {
			for (int y = 1; y <= m; y++) {
				if (x - w[y - 1] < 0)
				{
					dp[x][y] = dp[x][y - 1];
				}
				else {
					dp[x][y] = max(dp[x][y - 1], dp[x - w[y - 1]][y - 1] + v[y - 1]);
				}



			}
		}

		cout << dp[n][m] << endl;

	}

}