本文共 1025 字，大约阅读时间需要 3 分钟。

题目描述

辰辰是个天资聪颖的孩子，他的梦想是成为世界上最伟大的医师。为此，他想拜附近最有威望的医师为师。医师为了判断他的资质，给他出了一个难题。医师把他带到一个到处都是草药的山洞里对他说：“孩子，这个山洞里有一些不同的草药，采每一株都需要一些时间，每一株也有它自身的价值。我会给你一段时间，在这段时间里，你可以采到一些草药。如果你是一个聪明的孩子，你应该可以让采到的草药的总价值最大。”

如果你是辰辰，你能完成这个任务吗？

输入格式

第一行有 $2$ 个整数 $T$（$1\le T\le 1000$）和 $M$（$1\le M\le 100$），用一个空格隔开，$T$ 代表总共能够用来采药的时间，$M$ 代表山洞里的草药的数目。

接下来的 $M$ 行每行包括两个在 $1$ 到 $100$ 之间（包括 $1$ 和 $100$）的整数，分别表示采摘某株草药的时间和这株草药的价值。

输出格式

输入输出样例

70 371 10069 11 2

输出 #1

3

说明/提示

• 对于 $30\%$ 的数据，$M\le 10$；
• 对于全部的数据，$M\le 100$。
• NOIP2005 普及组第三题

解法 01背包

#include 
   
    using namespace std;const int MAXT = 1010, MAXM = 110;int T, M;int dp[MAXT], times[MAXM], vals[MAXM];int main() {
   	scanf("%d%d", &T, &M);	for (int i = 1; i <= M; ++i) scanf("%d%d", ×[i], &vals[i]);	for (int i = 1; i <= M; ++i) //对每株草药		for (int j = T; j >= times[i]; --j)			dp[j] = max(dp[j], dp[j - times[i]] + vals[i]);	printf("%d", dp[T]);	return 0;}
   

提交结果如下：

转载地址：https://memcpy0.blog.csdn.net/article/details/109890141 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！