【万题详解】P1048 [NOIP2005 普及组] 采药

题目描述

链接——题目在这里！！！

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

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

输入格式

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

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

输出格式

输出在规定的时间内可以采到的草药的最大总价值。

输入输出样例

输入 #1

70 3
71 100
69 1
1 2

输出 #1

3

说明/提示

【数据范围】

• 对于 30% 的数据，M≤10；

• 对于全部的数据，M≤100。

【题目来源】

NOIP 2005 普及组第三题

解题思路

这几乎是一道和01背包例题一模一样的水题！！！

动态规划是一种强大的计算模式，其解决问题的方式是首先定义一组子问题，按照从小问题解决大问题的模式，依次解决所有子问题并最终求解原问题。 所以我们来回顾一下

步骤

第一步：确定子问题。 在这一步重点是分析那些变量是随着问题规模的变小而变小的， 那些变量与问题的规模无关。

第二步：确定状态：根据上面找到的子问题来给你分割的子问题限定状态

第三步：推到出状态转移方程：这里要注意你的状态转移方程是不是满足所有的条件， 注意不要遗漏。

第四步：确定边界条件：先根据题目的限制条件来确定题目中给出的边界条件是否能直接推导出， 如果不行也可以尝试从边界条件反推（举个例子：a(n)→a(2)有递推关系， 但是a(2)→a(1)不符合上述递推关系， 我们就可以考虑用a(1)来倒推出a(2)， 然后将递推的终点设置为a(2)）;

第五步：确定实现方式：这个依照个人习惯 就像是01背包的两层for循环的顺序

第六步：确定优化方法：很多时候你会发现走到这里步的时候你需要返回第1步重来。首先考虑降维问题（优化内存）， 优先队列、四边形不等式（优化时间）等等。

几个背包的模板

1.无优化

for(int i=1;i<=n;i++){  for(int j=1;j<=m1;j++){   if(j>=t[i]){f[i][j]=max(f[i-1][j-t[i]]+m[i],f[i-1][j]);}else{f[i][j]=f[i-1][j];}}
}

2.空间优化

for(int i=1;i<=n;i++){  for(int j=m;j>=0;j--){  //--是为了防止叠加 if(j>=w[i]){  f[j]=max(f[j],f[j-w[i]]+c[i]);}	 }
}

3.常数优化

for(int i=1;i<=n;i++){sum+=w[i];b=max(m-sum,w[i]);for(int j=m;j>=bound;j--){if(j>=w[i]){f[j]=max(f[j],f[j-w[i]]+c[i]);}}
}

4.完全背包

for(int i=1;i<=n;i++){  for(int j=0;j<=m;j++){  if(j>=w[i]){  f[j]=max(f[j],f[j-w[i]]+c[i]);}	 }}

回到正题

这道题吧，本蒟蒻认为用最简单的无优化版二维数组就可以，当然空间优化的也可以。

状态转移方程：

1.无优化版cpp f[i][j]=max(f[i-1][j-t[i]]+m[i],f[i-1][j]);

2.空间优化版

f[j]=max(f[j],f[j-w[i]]+c[i]);

AC 

#include <iostream>
#include <cstring>
using namespace std;
const int N = 1010;
int f[N];
int main(){int n, m;cin >> n >> m;for(int i = 1; i <= m; i ++){int w, v;cin >> v >> w;for(int j = n; j >= v; j --){f[j] = max(f[j], f[j - v] + w);}}cout << f[n];return 0;
}

结尾

希望大家多多关注！！！

如果你能支持一下我，我十分感谢！！！

如果有人想在洛谷上做题，可以点下方链接：

https://www.luogu.com.cn/

如果你喜欢或想了解一下其他的算法，可以看看以下这些：

洛谷指南

洛谷使用指南_洛谷怎么看-CSDN博客

题目详解系列（部分）：

【万题详解】DFS搜索专题合集（上）-CSDN博客

【万题详解】P1314 [NOIP2011 提高组] 聪明的质监员-CSDN博客

【万题详解】洛谷P1282 多米诺骨牌-CSDN博客

【万题详解】洛谷P1238 走迷宫-CSDN博客

【万题详解】洛谷P1135奇怪的电梯-CSDN博客

【万题详解】洛谷P1510 精卫填海-CSDN博客

【万题详解】洛谷P1252 马拉松接力赛-CSDN博客

【万题详解】洛谷P1359 租用游艇-CSDN博客

【百题详解】洛谷P8508 做不完的作业-CSDN博客

【万题详解1】洛谷P1230 智力大冲浪-CSDN博客

【全网首发】洛谷贪心题解合集2-CSDN博客

【全网首发】洛谷贪心题解集合-CSDN博客

洛谷二分题集（3题）-CSDN博客

游戏系列：

C++棋类小游戏2-CSDN博客

C++自创棋类小游戏-CSDN博客

C++：史上最坑小游戏-CSDN博客

 C++：自创小游戏-CSDN博客

C++：下雪-CSDN博客

C++讲解系列（算法）：

C++：第十五讲高精度算法-CSDN博客

C++：第十四讲动态规划初步-CSDN博客

C++：第十三讲BFS广度优先搜索-CSDN博客

C++:第十二讲DFS深搜（二）_c++匿名函数dfs-CSDN博客

 C++：第十一讲DFS深搜-CSDN博客

C++：第十讲二分查找-CSDN博客

前缀和与差分：

C++：第九讲前缀和与差分-CSDN博客

贪心：

C++：第八讲贪心算法1-CSDN博客

C++讲解系列（基础入门）：

排序：

C++：第七讲冒泡排序-CSDN博客

函数：

C++第6讲max和min函数_c++ min函数-CSDN博客

C++第五讲函数初步-CSDN博客

for循环&数组：

C++第四讲for循环及数组-CSDN博客

if语句&else语句及运算：

C++第三讲：C++中的逻辑运算符及if else语句-CSDN博客

基础：

C++第二讲输入与输出-CSDN博客

C++第一讲认识C++编译器-CSDN博客

欢迎收看，希望大家能三连！

最后认识一下，我是爱编程的喷火龙廖，我们有缘再见！