实现的动态规划问题华为笔试题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

相关文章

好题——hdu2522(小数问题:求1/n的第一个循环节)

好喜欢这题,第一次做小数问题,一开始真心没思路,然后参考了网上的一些资料。 知识点***********************************无限不循环小数即无理数,不能写作两整数之比*****************************(一开始没想到,小学没学好) 此题1/n肯定是一个有限循环小数,了解这些后就能做此题了。 按照除法的机制,用一个函数表示出来就可以了,代码如下

hdu1043(八数码问题,广搜 + hash(实现状态压缩) )

利用康拓展开将一个排列映射成一个自然数,然后就变成了普通的广搜题。 #include<iostream>#include<algorithm>#include<string>#include<stack>#include<queue>#include<map>#include<stdio.h>#include<stdlib.h>#include<ctype.h>#inclu

【C++ Primer Plus习题】13.4

大家好,这里是国中之林! ❥前些天发现了一个巨牛的人工智能学习网站,通俗易懂,风趣幽默,忍不住分享一下给大家。点击跳转到网站。有兴趣的可以点点进去看看← 问题: 解答: main.cpp #include <iostream>#include "port.h"int main() {Port p1;Port p2("Abc", "Bcc", 30);std::cout <<

第10章 中断和动态时钟显示

第10章 中断和动态时钟显示 从本章开始,按照书籍的划分,第10章开始就进入保护模式(Protected Mode)部分了,感觉从这里开始难度突然就增加了。 书中介绍了为什么有中断(Interrupt)的设计,中断的几种方式:外部硬件中断、内部中断和软中断。通过中断做了一个会走的时钟和屏幕上输入字符的程序。 我自己理解中断的一些作用: 为了更好的利用处理器的性能。协同快速和慢速设备一起工作

C++包装器

包装器 在 C++ 中,“包装器”通常指的是一种设计模式或编程技巧,用于封装其他代码或对象,使其更易于使用、管理或扩展。包装器的概念在编程中非常普遍,可以用于函数、类、库等多个方面。下面是几个常见的 “包装器” 类型: 1. 函数包装器 函数包装器用于封装一个或多个函数,使其接口更统一或更便于调用。例如,std::function 是一个通用的函数包装器,它可以存储任意可调用对象(函数、函数

C++11第三弹:lambda表达式 | 新的类功能 | 模板的可变参数

🌈个人主页: 南桥几晴秋 🌈C++专栏: 南桥谈C++ 🌈C语言专栏: C语言学习系列 🌈Linux学习专栏: 南桥谈Linux 🌈数据结构学习专栏: 数据结构杂谈 🌈数据库学习专栏: 南桥谈MySQL 🌈Qt学习专栏: 南桥谈Qt 🌈菜鸡代码练习: 练习随想记录 🌈git学习: 南桥谈Git 🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈�

动态规划---打家劫舍

题目: 你是一个专业的小偷,计划偷窃沿街的房屋。每间房内都藏有一定的现金,影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警。 给定一个代表每个房屋存放金额的非负整数数组,计算你 不触动警报装置的情况下 ,一夜之内能够偷窃到的最高金额。 思路: 动态规划五部曲: 1.确定dp数组及含义 dp数组是一维数组,dp[i]代表

【C++】_list常用方法解析及模拟实现

相信自己的力量,只要对自己始终保持信心,尽自己最大努力去完成任何事,就算事情最终结果是失败了,努力了也不留遗憾。💓💓💓 目录   ✨说在前面 🍋知识点一:什么是list? •🌰1.list的定义 •🌰2.list的基本特性 •🌰3.常用接口介绍 🍋知识点二:list常用接口 •🌰1.默认成员函数 🔥构造函数(⭐) 🔥析构函数 •🌰2.list对象

【Prometheus】PromQL向量匹配实现不同标签的向量数据进行运算

✨✨ 欢迎大家来到景天科技苑✨✨ 🎈🎈 养成好习惯,先赞后看哦~🎈🎈 🏆 作者简介:景天科技苑 🏆《头衔》:大厂架构师,华为云开发者社区专家博主,阿里云开发者社区专家博主,CSDN全栈领域优质创作者,掘金优秀博主,51CTO博客专家等。 🏆《博客》:Python全栈,前后端开发,小程序开发,人工智能,js逆向,App逆向,网络系统安全,数据分析,Django,fastapi

让树莓派智能语音助手实现定时提醒功能

最初的时候是想直接在rasa 的chatbot上实现,因为rasa本身是带有remindschedule模块的。不过经过一番折腾后,忽然发现,chatbot上实现的定时,语音助手不一定会有响应。因为,我目前语音助手的代码设置了长时间无应答会结束对话,这样一来,chatbot定时提醒的触发就不会被语音助手获悉。那怎么让语音助手也具有定时提醒功能呢? 我最后选择的方法是用threading.Time