采药 （C++代码）

解题思路:

dp

注意事项:
1.优化二维数组至一维，就不需要写if判断了，否则需要像地表最强召唤兽那样写if，否则空间不足时的总价格就不会被计算还是0，导致答案错误

2.数组大小要开足

参考代码:

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#define N 1000

using namespace std;

int dp[N + 2], t[N + 2], c[N + 2];

int backPack01(int T, int n)
{
	for (int i = 1; i <= n; i++)
		for (int j = T; j >= t[i]; j--)
			dp[j] = max(dp[j], dp[j - t[i]] + c[i]);
	return dp[T];
}

int main(int argc, char** argv)
{
	int T, M;
	cin >> T >> M;
	for (int i = 1; i <= M; i++)
		cin >> t[i] >> c[i];
	cout << backPack01(T, M) << endl;
	return 0;
}