采药(详细分析(✪ω✪)(✪ω✪))

2023-11-24 19:10
文章标签 详细分析 采药

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

解题思路:

首先我们要创建两个数组储存采草药的时间以及采草药的价值,然后再创建一个二维数组用来储存在规定时间内所能采到草药的最大总价值。

时间:time[1050]={0};

价值:val[1050]={0};

二维数组:dp[1050][1050]={0};

 这个二维数组呢,先表示为dp[i][j],[i]这一部分就表示我们采摘草药的序号,[j]这一部分呢,就用来储存我们能够采摘的草药的价值了。

下面来我来为大家介绍一下如何使用这个二维数组

既然是二维数组,那使用它就一定要两个循环

 for(long long i=1;i<=m;i++){for(long long j=t;j>=0;j--){if(j>=time[i]){dp[i][j]=max(dp[i-1][j],dp[i-1][j-time[i]]+val[i]);}else dp[i][j]=dp[i-1][j];}}

这里的t,m就是题上所给的T,M的意思

最外层循环,由1到m,将每个草药都遍历一遍

第二层循环以及循环体,也就是本题的精华部分,j从t开始递减至0,目的就是为了让这个二维数组能够储存能够采到的草药的最大总价值

以样例为例,

 列出数组中所有的数据如下:

i\j

70

69

68

67

66

65

64

……

5

4

3

2

1

0

1

0

0

0

0

0

0

0

0

0

0

0

0

0

0

2

1

1

0

0

0

0

0

0

0

0

0

0

0

0

3

3

2

2

2

2

2

2

2

2

2

2

2

2

0

因为采摘第一个草药所需的时间为71,而总的采药时间为70,所以当i为1时,能够采摘到的草药的价值为0。

采摘第二个草药所需的时间为69,总的采药时间为70,所以当j>=69时,都可以获得这个草药的价值。

第三行的结果就要涉及到循环体了

            if(j>=time[i]){dp[i][j]=max(dp[i-1][j],dp[i-1][j-time[i]]+val[i]);}else dp[i][j]=dp[i-1][j];

这里的判断条件是“剩下的采摘时间j是否大于采摘第i株草药所需的时间time[i]”,如果大于,那么就要减去相应的时间,因为采摘草药总时间是一定的,采摘任何一株草药都会消耗,应该将该草药的价值加上上一行[j-time[i]]处草药的价值,并与上一行j处进行比较,确保在此时间点上所采的药的价值是最大的。

如果小于,那么将上一行的数据移下来就可以了。

那最后的答案就储存在dp[m][t]中。

总代码:

#include<iostream>
using namespace std;
long long dp[1050][1050]={0};
int main()
{long long t,m;long long time[1050]={0};long long val[1050]={0};cin>>t>>m;for(long long i=1;i<=m;i++){cin>>time[i]>>val[i];}for(long long i=1;i<=m;i++){for(long long j=t;j>=0;j--){if(j>=time[i]){dp[i][j]=max(dp[i-1][j],dp[i-1][j-time[i]]+val[i]);}else dp[i][j]=dp[i-1][j];}}cout<<dp[m][t];
}

希望各位大佬多提意见,不足之处还请指出。

也希望各位互相关注点赞,共同进步!Thanks♪(・ω・)ノ

这篇关于采药(详细分析(✪ω✪)(✪ω✪))的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

【Oracle篇】全面理解优化器和SQL语句的解析步骤(含执行计划的详细分析和四种查看方式)(第二篇,总共七篇)

💫《博主介绍》:✨又是一天没白过,我是奈斯,DBA一名✨ 💫《擅长领域》:✌️擅长Oracle、MySQL、SQLserver、阿里云AnalyticDB for MySQL(分布式数据仓库)、Linux,也在扩展大数据方向的知识面✌️ 💖💖💖大佬们都喜欢静静的看文章,并且也会默默的点赞收藏加关注💖💖💖 SQL优化续新篇,第二篇章启幕时。 优化器内藏奥秘,解析SQL步

25版王道数据结构课后习题详细分析 第八章 8.2 插入排序

一、单项选择题 ———————————————————— ———————————————————— 解析:直接插入排序在最坏的情况下要做n(n-1)/2次关键字的比较,当n=5时, 关键字的比较次数为10。注意不考虑与哨兵的比较。 正确答案: ———————————————————— ———————————————————— 解析:由于序列初始基本有序,因此使用直接插入排序

25版王道数据结构课后习题详细分析 第七章 7.5 散列表

一、单项选择题 ———————————————————— ———————————————————— 解析:顺序查找可以是顺序存储或链式存储;折半查找只能是顺序存储且要求关键字有序;树形查找法要求采用树的存储结构,既可以采用顺序存储也可以采用链式存储;散列查找中的链地址法解决冲突时,采用的是顺序存储与链式存储相结合的方式。 正确答案: ————————————————————

25版王道数据结构课后习题详细分析 第七章 7.4 B树和B+树

一、单项选择题 ———————————————————— ———————————————————— 解析:关键字数目比子树数目少1,首先可排除B+树。对于4阶B树,根结点至少有⒉棵子树(关键字数至少为1),其他非叶结点至少有n/2]=2棵子树(关键字数至少为1)至多有4棵子树(关键字数至多为3)。5阶B树和6阶B树的分析也类似。题目所示的B树,同时满足4阶B树、5阶B树和6阶B树的要

25版王道数据结构课后习题详细分析 第七章 7.3树形查找

一、单项选择题 ———————————————————— ———————————————————— 解析:二叉排序树插入新结点时不会引起树的分裂组合。对二叉排序树进行中序遍历可得到有序序列。当插入的关键字有序时,二叉排序树会形成一个长链,此时深度最大。在此种情况下进行查找,有可能需要比较每个结点的关键字,超过总结点数的1/2。 正确答案: ———————————————————

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]

JAVA开发(后端):微信小程序API调用详细分析及步骤

关键词:微信登录、统一下单(支付)、统一下单通知(回调)、统一下单查询、企业付款至零钱、支付查询、获取ACCESS_Token、获取小程序二维码   因为做项目涉及到微信这些接口的调用,尽管看了很多博客,比对了官方文档,仍还是踩了很多很多的坑,这里做一个记录及分享,提醒自己,帮助他人。文章如果有讲的不对得地方,欢迎指正。   首先根据官方文档分析流程,工具类见最后: 一、登录 官

25版王道数据结构课后习题详细分析 第六章 图 6.4图的应用

一、单项选择题 ———————————————————— ———————————————————— 解析: 正确答案: ———————————————————— ———————————————————— 解析: 正确答案: ———————————————————— ———————————————————— 解析: 正确答案: ——————————

C++项目详细分析_WebServer

前言 项目地址 项目介绍 源码详细分析 项目路径如下: 1.webserver.cpp 头文件和构造函数 #include "webserver.h"WebServer::WebServer(){// http_conn类对象users = new http_conn[MAX_FD];// root文件夹路径char server_path[200];getcwd(server_p

k8s-pod 实战三 (Liveness Probe 和 Readiness Probe 详细分析)

一、Liveness Probe 和 Readiness Probe 详细分析 Liveness Probe Liveness Probe 用于检查容器是否处于健康状态。如果探针失败,Kubernetes 会杀死容器并根据重启策略决定是否重启。这对于检测和恢复应用程序中的死锁或其他致命错误非常有用。 Readiness Probe Readiness Probe 用于检查容器是否准备好接受