html 网站开发软件,网站建设提供资料,洛阳网站建设好做不,重庆手机网站推广方法题目描述
链接——题目在这里#xff01;#xff01;#xff01;
辰辰是个天资聪颖的孩子#xff0c;他的梦想是成为世界上最伟大的医师。为此#xff0c;他想拜附近最有威望的医师为师。医师为了判断他的资质#xff0c;给他出了一个难题。医师把他带到一个到处都是草…题目描述
链接——题目在这里
辰辰是个天资聪颖的孩子他的梦想是成为世界上最伟大的医师。为此他想拜附近最有威望的医师为师。医师为了判断他的资质给他出了一个难题。医师把他带到一个到处都是草药的山洞里对他说“孩子这个山洞里有一些不同的草药采每一株都需要一些时间每一株也有它自身的价值。我会给你一段时间在这段时间里你可以采到一些草药。如果你是一个聪明的孩子你应该可以让采到的草药的总价值最大。”
如果你是辰辰你能完成这个任务吗
输入格式
第一行有 2 个整数 T1≤T≤1000和 M1≤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 i1;in;i){ for(int j1;jm1;j){ if(jt[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 i1;in;i){ for(int jm;j0;j--){ //--是为了防止叠加 if(jw[i]){ f[j]max(f[j],f[j-w[i]]c[i]);} }
}3.常数优化
for(int i1;in;i){sumw[i];bmax(m-sum,w[i]);for(int jm;jbound;j--){if(jw[i]){f[j]max(f[j],f[j-w[i]]c[i]);}}
}4.完全背包
for(int i1;in;i){ for(int j0;jm;j){ if(jw[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博客
欢迎收看希望大家能三连
最后认识一下我是爱编程的喷火龙廖我们有缘再见
