实现的动态规划问题华为笔试题C++实现

2024-09-08 05:20

本文主要是介绍实现的动态规划问题华为笔试题C++实现,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

秋招刷力扣题,我觉得我对动态规划不是熟练,在此处做总结

动态规划(Dynamic Programming,DP)算法通常用于求解某种具有最优性质的问题。在这类问题中,可能会有许多可行解,每一个解都对应一个值,我们希望找到具有最优值的解。我觉得最大的问题就是对问题的分解,分解后的问题与分解前的问题具有相同的决策机制,将决策机制进行抽象,最终可以得到对应的解;

动态规划中开始介绍的爬楼梯等问题,答案中会出现递归的方法,这让我一开始以为所谓的动态规划和递归都是从相求的结果开始,采用递归的方法;但是后来我看到剑指offer中说到,从最初的状态对结果进行求解才会避免多余的计算方式,因此出现这样一道题:

给你一个整数数组 coins ,表示不同面额的硬币;以及一个整数 amount ,表示总金额。计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额,返回 -1 。你可以认为每种硬币的数量是无限的。

对于求解的amount整数,可以求amount-coins[idx]最小,最终一步步递归求解,也可以用循环的方式从amount等于0一直求解到等于amount;

其次是华为秋招面试的一道动态规划的题,我大概描述一下我自己的想法:

        维修工要给n个客户更换设备,为每个用户更换一个设备。维修工背包内最多装k个设备,如果背包里有设备可以直接前往下一个客户更换或回公司补充设备,没有则需要回公司取设备。这些客户有优先级,维修工需要按照优先级给客户更换设备,优先级level用数字表示,数字小的优先级高。维修工从公司出发,给n个客户更换设备,最后再返回公司。请计算维修工完成这项工作所需要经历的最短总距离是多少。维修工可以走斜线。

  我在其中最大的问题就是,每个节点都可以回去,而且在某个节点回去之后都有可能导致最后的总的长度要小于在身上背的用完的时候大,然后我就纠结在一点很久,然后想了很久其实就是维修工再去找另一个用户到底会不会公司补充工具的问题,我过于纠结装备用不用完而不是选择上的问题,这就是我不会做动态规划问题的根本原因,我在对问题抽象的时候,经常把应该抽象在问题中的一个选择分支想做两个问题;下面我给出这一题我自己写的C++的答案,不一定对,只是自己的理解而已;

#include <iostream>
#include <cstdlib>  
#include <map>  
#include <vector>  
#include <string>  
#include <algorithm> 
#include <deque>  using namespace std;struct MyStruct
{int x;int y;int iLevel;
};struct MyStructState
{int idx;int volume;bool operator ==(const MyStructState& a){if (this->idx == a.idx && this->volume == a.volume)return true;return false;}};bool GreaterSort( MyStruct a,  MyStruct b)  // 重载sort函数的自定义比较函数comp
{return (a.iLevel < b.iLevel);}//map<int,map<int, double>>dp;
map<pair<int,int>,double>dp;
//map<MyStructState, double>dp;
vector<MyStruct> userInfoVec;
MyStruct comLocal;int sceneInfo[2];double calDis(MyStruct point1, MyStruct point2) {double distance= sqrt((point2.x - point1.x) * (point2.x - point1.x) + (point2.y- point1.y) * (point2.y - point1.y));return distance;
}double dfs(int idx,int volume,int userNums) {double temp;double distance;//if (dp.find(idx) != dp.end() && dp[idx].find(volume) != dp[idx].end())//	//	if (dp[{idx, volume}])return dp[{idx, volume}];distance = calDis(userInfoVec[idx], comLocal);if (idx == userNums - 1)return distance;temp = dfs(idx + 1, sceneInfo[1] - 1, sceneInfo[0]) + distance + calDis(comLocal, userInfoVec[idx + 1]);if (volume > 0)temp = min(temp, dfs(idx + 1, volume - 1, sceneInfo[0]) + calDis(userInfoVec[idx], userInfoVec[idx + 1]));dp[{idx, volume}] = temp;return temp;
}using namespace std;
int main() {MyStruct temp;//vector<MyStruct> userInfoVec;for (int i = 0; i < 2; i++) {cin >> sceneInfo[i];}cin >> comLocal.x;cin >> comLocal.y;int ilevel;for (int i = 0; i < sceneInfo[0]; i++) {cin >> temp.x;cin >> temp.y;cin >> temp.iLevel;userInfoVec.push_back(temp);}std::sort(userInfoVec.begin(), userInfoVec.end(), GreaterSort);printf("%f\n",( dfs(0,sceneInfo[1], sceneInfo[0]) + calDis(comLocal, userInfoVec[0])));}

这篇关于实现的动态规划问题华为笔试题C++实现的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

使用Python实现一个优雅的异步定时器

《使用Python实现一个优雅的异步定时器》在Python中实现定时器功能是一个常见需求,尤其是在需要周期性执行任务的场景下,本文给大家介绍了基于asyncio和threading模块,可扩展的异步定... 目录需求背景代码1. 单例事件循环的实现2. 事件循环的运行与关闭3. 定时器核心逻辑4. 启动与停

基于Python实现读取嵌套压缩包下文件的方法

《基于Python实现读取嵌套压缩包下文件的方法》工作中遇到的问题,需要用Python实现嵌套压缩包下文件读取,本文给大家介绍了详细的解决方法,并有相关的代码示例供大家参考,需要的朋友可以参考下... 目录思路完整代码代码优化思路打开外层zip压缩包并遍历文件:使用with zipfile.ZipFil

Python实现word文档内容智能提取以及合成

《Python实现word文档内容智能提取以及合成》这篇文章主要为大家详细介绍了如何使用Python实现从10个左右的docx文档中抽取内容,再调整语言风格后生成新的文档,感兴趣的小伙伴可以了解一下... 目录核心思路技术路径实现步骤阶段一:准备工作阶段二:内容提取 (python 脚本)阶段三:语言风格调

C#实现将Excel表格转换为图片(JPG/ PNG)

《C#实现将Excel表格转换为图片(JPG/PNG)》Excel表格可能会因为不同设备或字体缺失等问题,导致格式错乱或数据显示异常,转换为图片后,能确保数据的排版等保持一致,下面我们看看如何使用C... 目录通过C# 转换Excel工作表到图片通过C# 转换指定单元格区域到图片知识扩展C# 将 Excel

基于Java实现回调监听工具类

《基于Java实现回调监听工具类》这篇文章主要为大家详细介绍了如何基于Java实现一个回调监听工具类,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录监听接口类 Listenable实际用法打印结果首先,会用到 函数式接口 Consumer, 通过这个可以解耦回调方法,下面先写一个

使用Java将DOCX文档解析为Markdown文档的代码实现

《使用Java将DOCX文档解析为Markdown文档的代码实现》在现代文档处理中,Markdown(MD)因其简洁的语法和良好的可读性,逐渐成为开发者、技术写作者和内容创作者的首选格式,然而,许多文... 目录引言1. 工具和库介绍2. 安装依赖库3. 使用Apache POI解析DOCX文档4. 将解析

Qt中QGroupBox控件的实现

《Qt中QGroupBox控件的实现》QGroupBox是Qt框架中一个非常有用的控件,它主要用于组织和管理一组相关的控件,本文主要介绍了Qt中QGroupBox控件的实现,具有一定的参考价值,感兴趣... 目录引言一、基本属性二、常用方法2.1 构造函数 2.2 设置标题2.3 设置复选框模式2.4 是否

C++使用printf语句实现进制转换的示例代码

《C++使用printf语句实现进制转换的示例代码》在C语言中,printf函数可以直接实现部分进制转换功能,通过格式说明符(formatspecifier)快速输出不同进制的数值,下面给大家分享C+... 目录一、printf 原生支持的进制转换1. 十进制、八进制、十六进制转换2. 显示进制前缀3. 指

springboot整合阿里云百炼DeepSeek实现sse流式打印的操作方法

《springboot整合阿里云百炼DeepSeek实现sse流式打印的操作方法》:本文主要介绍springboot整合阿里云百炼DeepSeek实现sse流式打印,本文给大家介绍的非常详细,对大... 目录1.开通阿里云百炼,获取到key2.新建SpringBoot项目3.工具类4.启动类5.测试类6.测

pytorch自动求梯度autograd的实现

《pytorch自动求梯度autograd的实现》autograd是一个自动微分引擎,它可以自动计算张量的梯度,本文主要介绍了pytorch自动求梯度autograd的实现,具有一定的参考价值,感兴趣... autograd是pytorch构建神经网络的核心。在 PyTorch 中,结合以下代码例子,当你