算法模式---贪婪算法初识_贪婪的背包一个最多能承载重量为c=150的物品-程序员宅基地

技术标签: 读书笔记  逗比一下  

作为科班毕业的程序员,在下的代码能力感觉都是笑话。痛定思痛,决定啃一啃算法。发现好像都是大学的课本知识,摸摸头…尴尬。
当然不能一口吃一个胖子,这些仅作为入门学习

常用算法设计思想

常见分类

迭代法、贪婪法、穷举法搜索法、递推法、递归法、回溯法、分治法、动态规划法。

贪婪法 — 贪心算法

这种方法模式一般将求解过程分成若干个步骤,但每个步骤都最贪心,选择当前状态下收益最大,局部最有利的选择,并以此认定最后的结果也是最好的(最大的)

特点

贪婪法和动弹规划以及分治法一样,都需要对问题进行分解,定义最优解的子结构。
与其他方法不同之处在于,每一步选择完局部最优解就确定了,不再进行回溯了,也就是说,每个步骤确定后就不再修改了,直到算法结束。
但也因此很少情况下能得到最优解。

设计思想步骤

  • 建立对问题精准描述的数学模型,包括定义最优解的模型
  • 将问题分解为一系列的子问题,同时定义子问题最优解结构。
  • 引用贪心原则确定每个子问题的局部最优解,并根据其模型,用子问题局部模型堆叠出全局最优解

下面就是案例啦!累死我了

贪婪法例子:0-1背包问题

【问题描述】:有一个背包,最多能承载重量为 C=150 的物品,现在有 7 个物品(物品不能分割成任意大小),编号为 1~7,重量分别是 wi=[35、30、60、50、40、10、25],价值分别是 pi=[10、40、30、50、35、40、30],现在从这 7 个物品中选择一个或多个装入背包,要求在物品总重量不超过 C 的前提下,所装入的物品总价值最高。

常见的三种贪婪策略
1.根据物品价值选择,每次都选价值最高的物品
依次装入4,2,6,5,总重量是130,价值是165
2.根据物品重量选择最轻的物品,直到超过150
一次装入6,7,2,1,5,总重量140,总价值155
3.定义一个价值密度感念,SI=物品价值PI/物品重量WI
依次装入6,2,7,4,1,总重量150,价值170

三个方法都是正确的,但是第三种很明显模型设计的更好,所以效果很明显。

编程大赛的战旗游戏,贪心算法很明显被狠虐。实在是模型不太会设计。同样的模式老员工的建模会将各种欠款都考虑进去。所以,对战时候就像一个带眼睛一样。说多都是累啊,真累!!!

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/u010887126/article/details/83964843

智能推荐

Python生成图灵智能小助手,打发你工作生活中无聊时间_多功能助手python-程序员宅基地

文章浏览阅读163次。本文的文字及图片来源于网络,仅供学习、交流使用,不具有任何商业用途,版权归原作者所有,如有问题请及时联系我们以作处理本文章来自腾讯云 作者:Python进阶者想要学习Python?有问题得不到第一时间解决?来看看这里“1039649593”满足你的需求,资料都已经上传至文件中,可以自行下载!还有海量最新2020python学习资料。点击查看1 前言在家闲着,做个小项目,基于Python,实现一个语聊小机器人,分享给大家。项目整体比较简单,官方文档介绍的非常详细,可快速上手。2 目标将图灵_多功能助手python

如何正确学习数据结构、算法这门课?_如果让你来讲数据结构这门课,你准备怎么讲-程序员宅基地

文章浏览阅读1.2w次,点赞62次,收藏205次。你是否曾跟我一样,因为看不懂数据结构和算法,而一度怀疑是自己太笨?实际上,很多人在第一次接触这门课时,都会有这种感觉,觉得数据结构和算法很抽象,晦涩难懂,宛如天书。正是这个原因,让很多初学者对这门课望而却步。我个人觉得,其实真正的原因是你没有找到好的学习方法,没有抓住学习的重点。实际上,数据结构和算法的东西并不多,常用的、基础的知识点更是屈指可数。只要掌握了正确的学习方法,学起来并没有看上去那..._如果让你来讲数据结构这门课,你准备怎么讲

Mac用户速度来看!!Adobe 全家桶关闭自动更新?_illustrato关闭更新-程序员宅基地

文章浏览阅读1.1k次。有很多朋友在mac电脑上安装 Adobe 系列软件后,激活后过一段时间发现不能再使用,原来是 Adobe Creative Cloud 对软件进行了自动更新,自动更新后软件失去了激活,导致软件无法再使用。如果你发现 mac版photoshop,AE,PR突然不能使用了,请跟小编一起学学怎么关闭 Adobe Creative Cloud自动更新吧!Adobe 2020 Mac版全系列合集 「温馨提示:有会员的宝宝们可以下载哦」1、通过 Command+空格,输入creative cloud 快速启动._illustrato关闭更新

thrift源码解析——深度学习模型的服务器端工程化落地方案_java项目深度学习算法工程化-程序员宅基地

文章浏览阅读401次。来源 | 极链AI云(性价比最高的共享GPU算力平台,双十活动进行中 10.9-10.11,充值就送!最多可送2500元现金券!免费试用地址:https://cloud.videojj.com/)文章来源:https://cloud.videojj.com/bbs/topic/28/thrift源码解析-深度学习模型的服务器端工程化落地方案/2有了训练好的模型,怎么用服务调用?很多人可能会想到用flask进行http调用。那如果是内网呢?如果希望去掉http封包解包一系列耗时操作呢?自然我们会._java项目深度学习算法工程化

Activiti 变量设置-程序员宅基地

文章浏览阅读94次。  使用工作流的时候必定会附上一些变量。例如,请假的时候有填写请假理由,天数等等。可以用以下代码实现  public void setVariables(){ /**与任务(正在执行)*/ TaskService taskService = processEngine.getTaskService(); //任务ID ..._activiti 数组变量设置

Codeforces Round #717 (Div. 2)A-B详解_xooo3-程序员宅基地

文章浏览阅读248次。题目链接:https://codeforces.com/contest/1516A.Tit for Tat题意:给定一个数组,然后再给定n和k。你可以执行操作如下:给任意两个不同的元素(下标不同)一个加上1,一个减掉1。最多执行k次这样的操作,请你给出一个字典序最小的数组。..._xooo3

随便推点

vue 一个页面使用多个wangEditor并删除_wangeditor删除配置项-程序员宅基地

文章浏览阅读2.1k次。<template lang="html"> <div class="editor"> <div ref="toolbar" class="toolbar"> </div> <div ref="editor" class="text"> </div> <el-button @..._wangeditor删除配置项

HTML <th> 标签_<th>l-程序员宅基地

文章浏览阅读454次。HTML <th> 标签什么是<th> 标签?定义表格内的表头单元格。HTML 表单中有两种类型的单元格:表头单元格 ‐ 包含表头信息(由 th 元素创建)标准单元格 ‐ 包含数据(由 td 元素创建)实例普通的 HTML 表格,包含两行两列:<table cellspacing=“0”><tr><th>姓名</th><th>成绩</th></tr> &_l

Java中Default关键字的两种使用方法,以及Java8新特性interface中的static方法和default方法_interface 的defaullt方法关键字时从jdk8版本开始引起的-程序员宅基地

文章浏览阅读531次。Java中Default关键字的两种使用方法Java8新特性(一)_interface中的static方法和default方法_interface 的defaullt方法关键字时从jdk8版本开始引起的

一次前端面试_一次前端的面试-程序员宅基地

文章浏览阅读437次。我的第一篇输出2020年8月前端面试从事前端开发一段时间了,开发水平一直都没有什么提高。最近疫情被隔离在家,反省了一下自己的工作日常,觉得自己的学习方法有问题。一直有输入,但是从来没有输出。今天鼓起勇气,开始写我的第一篇输出。一是为了加深对知识的理解,二是对知识做一个总结和归纳。我的文章内容都是为了总结个人的知识点,如果有理解不正确的地方希望大家可以帮我纠正,我会积极理解消化,希望和大家共同进步。2020年8月前端面试1、es6里的promise有几种状态?可以解决什么问题?1.1 状态:① p_一次前端的面试

C++ XML-程序员宅基地

文章浏览阅读70次。写Unmanaged Code在.NET时代成为一种很悲惨的事,当你需要处理XML文件时,这种感觉会变得尤其强烈。FCL中的System.Xml多简单啊,连Steve Ballmer都知道怎么用。事情不会总是那么理想的,如果你要在C/C++程序里处理XML怎么办呢?选择一:市面上的XML lib还是有几个的,最有名的当然是libxml。我一年前用过,很不错,我还特意写了一份简明教程..._xmlfile->load(varxml, &varout)

Mac教程:如何开启任何来源选项_开启所有来源csdn-程序员宅基地

文章浏览阅读727次。最近很多朋友咨询关于Mac如何开启任何来源选项的问题,今天小编就和大家聊一聊这个话题,希望可以帮助到大家。使用Mac电脑安装或运行软件,你是否遇到提示该镜像已损坏,请移至废纸篓的问题呢?这有可能是你的电脑系统在系统偏好设置中关闭了任何来源选项,如何开启任何来源选项呢?小编带来了Mac电脑开启任何来源选项教程,一起来看看吧!如何查看是否开启点击左上角的系统偏好设置2. 点击安全与隐私3. 点击通用如何开启按照图示1.2.3打开Spotlight,输入终端然后按下enter键2. 复制sudo spc_开启所有来源csdn

推荐文章

热门文章

相关标签