【采药.】

2023-12-25 08:20
文章标签 采药

本文主要是介绍【采药.】,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

采药

题目链接

题意

在这规定时间内采摘草药,使得获得的草药总价值最大(动态规划)

思路

  1. 初始化数组并输入
  2. 动态规划
  3. 输出

坑点

  1. 容易忘记初始化

算法一:动态规划

时间复杂度

O(n * T)

实现步骤
  1. 输入
  2. 动态规划
  3. 输出
代码
#include <iostream> 
using namespace std;
int a[10010],b[10010],f[10010];   
//每株草药的采摘时间、价值以及最优解数组
int main() 
{int t,n;   //总时间和草药的数目   cin>>t>>n;for(int i=1; i<=n; i++){cin>>a[i]>>b[i];}//读取每株草药的采摘时间 a[i] 和价值 b[i],并存储在数组 a 和 b 中for(int i=1; i<=n; i++){for{(int j=t; j>=a[i]; j--)f[j]=max(f[j-a[i]]+b[i],f[j]);}}//两个嵌套循环实现动态规划。外层循环遍历每株草药,内层循环遍历每个时间点:从总时间 t 递减到当前草药的采摘时间 a[i]。对于每个时间点 j,代码计算如果不采摘当前草药和采摘当前草药的两种情况下的最大价值,并更新数组 f 中的相应值。cout<<f[t];      //输出结果
}

总结

动态规划问题,初始化一个数组来存储每个时间点的最大价值,并遍历所有草药和时间点来更新这个数组,最后输出总时间内的最大价值。

这篇关于【采药.】的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/534841

相关文章

P1616 疯狂的采药(完全背包模板)

//这是一道完全背包的题,并且需要用一维数组优化空间,否则会MLE #include <bits/stdc++.h>using namespace std;//t表示可以用来采药的时间(相当于背包容量)//m表示草药的数目(相当于物品数量)int t, m; //m<=10^4,t<=10^7 //w[i]表示采摘第i种草药需要花费的时间(相当于背包模型中物品的体积) //v[i]

采药问题 01背包

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

采药(信息学奥赛一本通-T1290)

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

疯狂的采药(洛谷-P1616)

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

采药(洛谷-P1048)

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

采药【(0-1)背包问题】

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

秋招突击——算法打卡——5/31——复习{采药问题、(状态压缩DP)小国王}——新做:{盛最多水的容器、整数转罗马数字}

文章目录 复习背包模型——采药问题状态压缩DP——小国王思路分析实现代码参考 新作盛最多的水个人实现思路分析实现代码 参考分析思路分析实现思路 整数转罗马数字个人实现思路分析实现代码 参考实现思路分析实现代码 总结 复习 背包模型——采药问题 原题链接这里回忆的时候,还是有点问题,就是起点值怎么写?并不确定!然后关于这个表达式,也是弄了半天才想起来,还是要多多练习一下

【NC16650】采药

题目 采药 动态规划-01背包 思路 01背包例题,思路见同一专栏的【NC16693】装箱问题,这里只贴出代码。 代码 #include <stdio.h>int max(int a, int b) { return a > b ? a : b; }int main(void) {int n = 0, m = 0;scanf("%d%d", &n, &m);// a[m][2]

采药NOIP2005J

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

洛谷 P1048 [NOIP2005 普及组] 采药

本文由Jzwalliser原创,发布在CSDN平台上,遵循CC 4.0 BY-SA协议。 因此,若需转载/引用本文,请注明作者并附原文链接,且禁止删除/修改本段文字。 违者必究,谢谢配合。 个人主页:blog.csdn.net/jzwalliser 题目 洛谷 P1048 [NOIP2005 普及组] 采药 [NOIP2005 普及组] 采药 题目描述 辰辰是个天资聪颖的孩子,他的梦