如何采药才最值当——记忆化搜索

学无止境，日日进步，勤奋刻苦，方能得胜，打破思维壁垒，开拓新视界，坚持就是胜利，追求卓越，人生无悔。

文章目录

  • 引言
  • 正文
    • 爆搜思路
      • 代码
    • 记忆化搜索思路
      • 代码
    • 递推思路
      • 代码
    • 总结
    • 如何写出记忆化搜索

引言

这是一个悬壶济世的故事。据说神农尝百草后，将自己的收获撰写成一本书，分发给各个部落的长老。有一天，一个部落里面忽然爆发了各种疾病，为了遏制疾病，部落长老出去寻找能治病的草药。历经千辛万苦，他终于找到了一片福地，这里面的草药应有尽有，然而，有些药近在眼前，能很容易地找到；有些药则远在天边，需要花费很多天才能找到。假设长老知道所有草药的位置，并且能确定采到药的时间，每种药只能救活特定人数的人，且他只有有限的时间用来寻找草药，那么，他该如何采药，才能救活更多的人呢？

正文

首先，我们可以确定的是，爆搜肯定能帮助长老找到最优解，但长老很赶时间，等到爆搜完，村里的人可能都死光光了~所以要找到时间更短的方法。我们思考这样一个问题：总共只有这么几种药，几块地方，爆搜搜来搜去肯定会有一模一样的情况出现。如果我们记住第一次搜索这种情况的答案，等到第二次搜索的时候直接用，是不是就能有效减少搜索的时间了呢？我们按照这个思路写一下：

爆搜思路

如果爆搜的话，我们就直接考虑这个题涉及到多少变量就可以了。显然，题目中包含三种变量：

  1. 搜索每种草药的时间
  2. 每种草药能救活多少人
  3. 长老采药的时间限制
    我们直接爆搜这三种变量就可以：

代码

#include<algorithm>
#include<iostream>
using namespace std;
int* time1;//采每种药花费的时间
int* price;//每种药的价值
int sum_time=100;//长老剩余的采药时间
int now_val=0;//现有草药的价值
int n;//草药种数
int ans;//现在的解
int dfs(int i,int sum_time,int now_val)
{if (sum_time < 0)return;if (i == n + 1) {//每次搜索完如果符合条件则更新解ans = max(ans, now_val);return;}//依次枚举采该种药和不采该种药的情况dfs(i + 1, sum_time, now_val);dfs(i + 1, sum_time - time1[i], now_val + price[i]);
}

记忆化搜索思路

爆搜算法的时间复杂度是指数级的，肯定行不通。于是我们按照上文思路，记住上一次搜索的答案，在下一次直接用就可以。另外当前采药的价值是由前两种变量决定的，因此可以只搜索两个变量，每次将第三个变量的答案通过数组存起来就可以了。
这种减少维度的思想在合并石头的最低成本中也用到过。

代码

#include<algorithm>
#include<iostream>
using namespace std;
int* time1;//采每种药花费的时间
int* price;//每种药的价值
int sum_time=100;//长老剩余的采药时间
int** now_val;//用二维数组来存储第i种草药采或不采的价值
int n;//草药种数
int ans;//现在的解
int dfs(int i,int sum_time)//搜索第i种草药，省去了第三个变量，改用数组存储。
{if (sum_time < 0)return;if (now_val[i][sum_time] != -1) {return now_val[i][sum_time];}if (i == n + 1)now_val[i][sum_time] = 0;int dfs1, dfs2;dfs1 = dfs(i + 1, sum_time);dfs2 = dfs(i + 1, sum_time - time1[i])+price[i];return now_val[i][sum_time] = max(dfs1, dfs2);
}

递推思路

分析一下，这道题满足动态规划的三个特征：

  1. 最优子结构：大问题的最优解是所有小问题最优解的最大值
  2. 无后效性：不能回头去采已经采过的药
  3. 重叠子问题：我们分析记忆化搜索的时候就知道肯定会有完全一样的子问题。
    因此可以用动态规划的方法解决。

代码

#include<algorithm>
#include<iostream>
using namespace std;
int* time1;//采每种药花费的时间
int* price;//每种药的价值
int sum_time=100;//长老剩余的采药时间
int** now_val;//用二维数组来存储第i种草药采或不采的价值
int n;//草药种数
int ans;//现在的解
int dp()
{for (int i = 0; i < n; i++) {for (int j = sum_time; j >=0; j++) {//起始状态是从第0种草药开始选择，剩余时间为初始的sum_timeif (j >= time1[i]) {now_val[i][j] = max(now_val[i - 1][j], now_val[i - 1][j + time1[i]] + price[i]);//不采或采}else {now_val[i][j] = now_val[i - 1][j];//只能选择不采}}}
}

总结

简要比较一下记忆化搜索和递推代码，你会发现他们的答案都是通过比较两个东西的最大值来得出的，而且这两个东西都是之前求好的，所以他们的思维方式及其相似，都使用了空间换时间的思想，时间复杂度也是差不多的。
与动态规划相比，记忆化搜索比较好写，无需考虑状态转移方程，而且处理边界比较方便（上文的记忆化只用了一个if条件来处理）。但是由于存在递归，因此效率会低于动态规划，而且难以优化，需要取舍。

如何写出记忆化搜索

上文是从爆搜代码优化到记忆化搜索的，我们可以总结为：

  1. 写出爆搜代码
  2. 减小维度，去除不必要变量
  3. 写出存储数组

当然也可以从动态规划到记忆化搜索：

  1. 写出dp代码
  2. 用状态转移方程写出对应的dfs函数
  3. 写出存储数组

————————分割线——————————

我是霜_哀，在算法之路上努力前行的一位萌新，感谢你的阅读！码文不易，如果觉得好的话，可以关注一下，我会在将来带来更多更全面的算法讲解！

查看全文

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.dgrt.cn/a/2281846.html

如若内容造成侵权/违法违规/事实不符，请联系一条长河网进行投诉反馈，一经查实，立即删除！

相关文章：

如何采药才最值当——记忆化搜索

学无止境，日日进步，勤奋刻苦，方能得胜，打破思维壁垒，开拓新视界，坚持就是胜利，追求卓越，人生无悔。 文章目录引言正文爆搜思路代码记忆化搜索思路代码递推思路代码总结如何写出记忆化……

编程日记2023/4/11 16:01:13

JVM：并发的可达性分析

当前主流编程语言的垃圾收集器基本上都是依靠可达性分析算法来判定对象是否存活的，可达性分析算法理论上要求全过程都基于一个能保障一致性的快照中才能够进行分析，这意味着必须全程冻结用户线程的运行。
在根节点枚举这个步骤中，由于 GC Ro……

编程日记2023/4/11 16:00:48

一文讲解电源技术中的安森美深力科CAT6219-330TDGT3 500 mA，带快速启动 LDO稳压器 详情讲解

一文讲解电源技术中的安森美深力科CAT6219-330TDGT3 500 mA，带快速启动 LDO稳压器 详情讲解
CAT6219-330TDGT3是一款 500 mA CMOS 低漏稳压器，在负载电流和线路电压变化期间提供快速响应时间。 快速启动特性允许使用外部旁通电容器，可降低总……

编程日记2023/4/11 16:00:34

解决Ubunt20.04安装Sogou输入法失败进不去桌面 及 中文输入法安装

目录解决Ubunt20.04安装Sogou输入法失败进不去桌面中文输入法安装解决wps无法输入中文解决Ubunt20.04安装Sogou输入法失败进不去桌面
问题： Ubuntu20.04 安装了 fcitx 和 sogou 输入法；键盘输入法系统由 IBus 改成了 fcitx；重启后可以出现登……

编程日记2023/4/11 16:00:25

从java到JavaScript(2)：对比Java/Go/Swift/Rust看Dart

Dart与Java的一些直观区别
Dart和java以及C#都差不多，基本上不用学习可以直接使用，从这里可以你可以了解Dart有些特别之处。其实对于Java开发人员来说Dart，还是相对好理解的
基本语法对比：
关键字 在 Dart 中没有诸如 public、……

编程日记2023/4/11 16:00:13

单体架构的缺点是什么?

随着互联网技术的发展，传统的应用架构已满足不了实际需求，微服务架构就随之产生。那么传统应用架构到底出了什么问题呢?又如何解决?接下来我们将从传统单体架构的问题开始，对为什么需要微服务架构进行详细讲解。
传统单体应用架构的问题
……

编程日记2023/4/11 16:00:01

IM即时通讯-7-如何设计通知提醒

本文大纲
本文从为什么做通知提醒， 以及如何设计通知提醒， 以及如何衡量通知提醒三方面解释了如何设计通知提醒。 对于重点的如何设计通知提醒， 通过拆分前台和后台， 前台采用自建或者二方通道， 后台采用厂商信令通道……

编程日记2023/4/11 15:59:38

Linux初学(CnetOS7 Linux)之切换命令模式

通常我们也称命令模式为终端机接口,terminal 或 console 。
Linux 预设的情况下会提供六个 Terminal 来让使用者登入， 切换的方式为使用：[Ctrl] [Alt] [F1]~[F6]的组合按钮。
那这六个终端接口如何命名呢，系统会将[F1] ~ [F6]命名为 tty1……

编程日记2023/4/11 15:59:27

CocosCreator实战篇 ｜CocosCreator实现《飞机大战》

📢博客主页：肩匣与橘 📢欢迎点赞 👍 收藏 ⭐留言 📝 如有错误敬请指正！ 📢本文由肩匣与橘编写，首发于CSDN🙉 📢生活依旧是美好而又温柔的，你也……

编程日记2023/4/11 15:59:16

使用docker-compose搭建mysql主从

目录
一、docker-compose和主从的简介
1、docker-compose
2、mysql主从
3、为什么要使用docke-compose？
二、部署mysql主从集群
1、mysql-master主库
2、mysql-slave从库
三、安装docker-compose
1、上传文件
2、添加可执行权限
3、创建并编辑docker-com……

编程日记2023/4/11 15:59:06

vue2+vue3

vue2vue3尚硅谷vue2vue2 课程简介【02:24】vue2 Vue简介【17:59】vue2 Vue官网使用指南【14:07】vue2 搭建Vue开发环境【13:54】vue2 Hello小案例【22:25】了解： 不常用常用：id 更常用 简单class差值总结vue 实例vue 模板 ： 先 取 &#xff0……

编程日记2023/4/16 14:52:00

【hello Linux】环境变量

目录 1. 环境变量的概念 2. 常见的环境变量 3. 查看环境变量 4. 和环境变量相关的命令 5. 环境变量的组织方式 6. 通过代码获取环境变量 7. 通过系统调用获取环境变量 Linux🌷 在开始今天的内容之前，先来看一幅图片吧！ 不知道你们是否和我一……

编程日记2023/4/16 14:51:36

【Linux基础】常用命令整理

ls命令
-a选项，可以展示隐藏的文件和文件夹-l选项，以列表形式展示内容-h，需要和-l搭配使用，可以展示文件的大小单位ls -lah等同于la -a -l -h
cd命令（change directory）
语法：cd [Linux路径]……

编程日记2023/4/16 14:51:26

客快物流大数据项目（一百一十二）：初识Spring Cloud

文章目录
初识Spring Cloud
一、Spring Cloud简介
二、SpringCloud 基础架构图…

编程日记2023/4/16 14:51:11

C和C++中的struct有什么区别

区别一： C语言中： Struct是用户自定义数据类型（UDT）。 C语言中： Struct是抽象数据类型（ADT），支持成员函数的定义。
区别二：
C中的struct是没有权限设置的&#xff0c……

编程日记2023/4/16 14:50:59

docker的数据卷详解

数据卷 数据卷是宿主机中的一个目录或文件，当容器目录和数据卷目录绑定后，对方修改会立即同步
一个数据卷可以同时被多个容器同时挂载，一个容器也可以被挂载多个数据卷
数据卷作用：容器数据持久化 /外部机器和容器间接通信 /容器……

编程日记2023/4/16 14:50:50

13、Qt生成dll-QLibrary方式使用

Qt创建dll，使用QLibrary类方式调用dll
一、创建项目
1、新建项目->其他项目->Empty qmake Project->Choose 2、输入项目名，选择项目位置，下一步 3、选择MinGW，下一步 4、完成 5、.pro中添加TEMPLATE subdirs&#xff……

编程日记2023/4/16 14:50:38

基于mapreduce 的 minHash 矩阵压缩

Minhash作用： 对大矩阵进行降维处理，在进行计算俩个用户之间的相似度。
比如： 俩个用户手机下载的APP的相似度，在一个矩阵中会有很多很多的用户要比较没俩个用户之间的相似度是一个很大的计算任务 如果首先对这个矩阵降维处理&am……

编程日记2023/4/16 14:50:37

关于hashmap使用迭代器的问题

keySet获得的只是key值的集合，valueSet获得的是value集合，entryset获得的是键值对的集合。 package com.test2.test;import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
import java.util.Map.Entry;public class mapiterator……

编程日记2023/4/16 14:50:37

Hadoop入口FileSystem HDFS操作 本地文件合并到HDFS和HDFS文件合并

Hadoop 文件API的起点是FileSystem类。这是一个与文件系统交互的抽象类。存在不同的具体实现子类来处理HDFS和本地文件系统。
HDFS接口的FileSystem对象：
Configuration conf new Configuration();
FileSystem hdfs FileSystem.get(conf); HDFS直接操作&#x……

编程日记2023/4/16 14:50:36

Published by

风君子

独自遨游何稽首 揭天掀地慰生平

发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注