当前位置: 首页 > news >正文

动态规划--背包问题

动态规划

  • 背包问题
    • 算法思路
    • 代码实现

背包问题

假设你要去野营。你有一个容量为6磅的背包,需要决定该携带下面的哪些东西。其中每样东西都有相应的价值,价值越大意味着越重要:
 水(重3磅,价值10)
 书(重1磅,价值3)
 食物(重2磅,价值9)
 夹克(重2磅,价值5)
 相机(重1磅,价值6)
请问携带哪些东西时价值最高?

算法思路

参考: 《算法图解》p142
Value = Max( v1, v2)
Value – 最高价值
v1 = 当前物品的价值 + 剩余空间的价值
v2 = 同样空间排除当前物品的价值


比如一共5种物品, 按顺序当前是“相机”,
Value[5,6] :5种物品,空间为6磅。
v1 = 6 + Value[4,5]
相机的价值为 6
剩余空间为 6磅 - 1 磅 = 5 磅

v2 = Value[4,6]
在空间为6磅的情况下, 不选相机的最大价值。


代码实现

from copy import deepcopydef dynamic(gdict:dict, w:int):if len(gdict) == 1:k,its = gdict.popitem()n,v = its.popitem()if w >= n:return k,vreturn "",0else:k,its = gdict.popitem()n,v = its.popitem()newitem = deepcopy(gdict)if w>=n:name, s = dynamic(gdict, w-n)value = v +sres = "%s,%s"%(k,name)else:name,s = dynamic(gdict, w)value = sres = "%s"%namenewname,news = dynamic(newitem, w)if news > value:return newname, newsreturn res,valuegoods = dict()
goods["water"] = {3:10}
goods["book"] = {1:3}
goods["food"] = {2:9}
goods["jack"] = {2:5}
goods["camera"] = {1:6}
bags = 6print(dynamic(goods, bags))

相关文章:

动态规划--背包问题

动态规划背包问题算法思路代码实现背包问题 假设你要去野营。你有一个容量为6磅的背包,需要决定该携带下面的哪些东西。其中每样东西都有相应的价值,价值越大意味着越重要:  水(重3磅,价值10)  书&…...

从0开始学python -45

Python3 正则表达式 -3 正则表达式对象 re.RegexObject re.compile() 返回 RegexObject 对象。 re.MatchObject group() 返回被 RE 匹配的字符串。 start() 返回匹配开始的位置end() 返回匹配结束的位置span() 返回一个元组包含匹配 (开始,结束) 的位置 正则表达式修饰符…...

如何用BurpSuite抓取手机数据包

文章目录前言准备工具Burp Suite物理机或虚拟机(移动设备)手机抓包网络环境开启burp并设置代理手机配置代理安装Burp证书开始抓包踩坑后记前言 最近挖了一波src,挖来挖去发现有很多公众号或者app没有测试,这就需要Burp能够抓取手机的数据包了&#xff0…...

Linux性能监控工具iostat解析

1.iostat命令详解 CPU 内存 磁盘 网络 四大子系统 1.1 查看提供iostat命令的软件包 yum provides "*/iostat" yum -y install systatiostat 1 显示实时的数据 iostat 结果自系统启动以来的平均值1.2 iostat命令CPU指标 %user 应用程序消耗CPU资源占比 %nice 进…...

3D可视化大屏制作真的那么难?没有好用的软件解决吗?

有多少人印象里的数据可视化大屏还是像这样的二维大屏?这种二维可视化大屏早就不能满足审美日益提高的大众了。 现在用的都是3D可视化大屏,这种结合了3D技术的可视化形式不仅让数据更加的清晰,也增加了美感,这观看体验&#xff…...

C语言|文件读写,代码运行后留下“记忆”

前言对于一个代码,运行时可能需要保留产生的结果,例如计算值,筛选值,记录点或者小游戏的得分,而正常情况下我们要保存一个数据,想到的肯定是打开我们的文本软件,手撸文字,今天这篇文…...

【2023unity游戏制作-mango的冒险】-6.关卡设计

👨‍💻个人主页:元宇宙-秩沅 hallo 欢迎 点赞👍 收藏⭐ 留言📝 加关注✅! 本文由 秩沅 原创 收录于专栏:unity游戏制作 ⭐mango的冒险关卡设计⭐ 文章目录⭐mango的冒险关卡设计⭐👨‍&#…...

JavaScript高级 浏览器WebStorage

WebStorage主要提供了一种机制,可以让浏览器提供一种比cookie更直观的key、value存储方式: localStorage:本地存储,提供的是一种永久性的存储方法,在关闭掉网页重新打开时,存储的内容依然保留; …...

$ 3 :类型强制转换场景、printf函数

1、类型强制转换场景 #include <stdio.h> //强制类型转换 int main() {int i=5;float j=i/2;float k=(float)i/2;printf("%f\n",j);printf("%fln",k);return 0;} j得到的值为2,k得到的值是2.5,因为当我们整数做除法时,默认进行整除,要得到小数,…...

视频会议系统异常中断故障分析案例

1. 背景 某电气化局的用户反馈&#xff0c;近期视频系统在使用过程中出现频繁中断的情况&#xff0c;这种情况影响到用户的视频体验和工作效率。 针对此问题&#xff0c;我们将NetInside流量分析系统部署到电气化局机房&#xff0c;使用流量分析系统提供实时和历史原始流量。…...

什么是文件传输中台?

企业文件传输的场景有哪些&#xff1f; 企业日常办公中无时无刻不在产生数据文件。多样化的数据已成为企业的重要资产&#xff0c;更被称为是“新石油”。数据并不是单单存储起来就行了&#xff0c;而是需要高效又安全的让数据流转起来&#xff0c;释放其自身的价值&#xff0…...

设计模式-代理模式(Java)

本篇文章详细说明代理模式并用代码简单介绍代理模式的用法&#xff0c;以及代理模式在实际应用中的源码简单解析。 1、什么是代理模式和代码实现 代理模式是一种设计模式&#xff0c;它允许在不改变原有类的情况下&#xff0c;为其提供一种代理机制&#xff0c;用于控制其访问…...

如何处理负面评论?利用负面评论发挥优势

每家公司都应该做的一件事&#xff1a;回复评论&#xff01; 37%的买家积极考虑对评论的回应&#xff0c;以评估和对品牌的看法。所以不要忘记回复评论&#xff01; 如何处理负面评论 如果您的公司正在经历大量负面评论&#xff0c;请了解您的产品团队如何利用它们来发挥自己的…...

一个JAVA程序员必备的技能有哪些?知道这些帮你快速升职加薪

和其他行业一样&#xff0c;软件研发行业也有必须要掌握的工具&#xff0c;每个程序员只有学习了这些工具之后才会不断成长&#xff0c;今天就和大家分享一些程序员必备的十项技能。老实说&#xff0c;如果每个程序员都非常了解这些工具&#xff0c;那么他可以在日常工作中完成…...

DHTMLX Suite 8.0 重大发布,新增更多新主题、热图图表、辅助功能支持功能

DHTMLX Suite 是一个用于构建跨浏览器Web应用和移动应用的强大JavaScript UI库。DHTMLX UI 组件库允许您更快地构建跨平台、跨浏览器 Web 和移动应用程序。它包括一组丰富的即用式 HTML5 组件&#xff0c;这些组件可以轻松组合到单个应用程序界面中。 DHTMLX Spreadsheet正版试…...

[华为OD机试 ] Linux发行版的数量(C++ Java JS Python)

文章目录 题目描述输入描述输出描述备注用例题目解析C++JavaScriptJavaPython题目描述 Linux操作系统有多个发行版,distrowatch.com提供了各个发行版的资料。这些发行版互相存在关联,例如Ubuntu基于Debian开发,而Mint又基于Ubuntu开发,那么我们认为Mint同Debian也存在关联…...

HydroD 实用教程(五)Morsion Model

目 录一、前言二、Morison 方程三、Morison 单元与属性3.1 Anchor Elements3.2 Pressure Area Elements3.3 TLP Elements3.4 Morison 3D Elements3.5 Morison (2D) Sections四、Element Correspondence五、参考文献一、前言 SESAM &#xff08;Super Element Structure Analysi…...

成功解决xshell7会话窗口只能显示一个的问题

文章目录前言一. 问题复现二. 问题解决方法一方法二三. 拓展3.1 自定义快捷键3.2 将当前shell中的代码内容复制到记事本中3.3 xshell配置密钥登录3.3.1 生成密钥3.3.2 将密钥上传到服务器并设置3.3.3 用xshell密钥登录服务器总结前言 重点强调&#xff1a; 本文是解决xshell的…...

Spring security 个人理解

改文章写的很好&#xff1a;https://zhuanlan.zhihu.com/p/342755411 Spring security 分为两个部分 登陆认证权限认证 登陆认证 其实就是就是登陆注册&#xff0c;然后获取登陆凭证的问题 操作如下 登陆账号密码&#xff0c;通过账号查询出用户数据&#xff0c;然后密码进…...

线性表 顺序表数组

初识线性表 文章目录初识线性表线性表的类型定义基本操作&#xff08;一&#xff09;init&#xff0c;destory&#xff0c;clear基本操作&#xff08;二&#xff09; 判空 &#xff0c;求长基本操作&#xff08;三&#xff09;取值&#xff0c;取位置基本操作&#xff08;四&am…...

老设备焕新:OCLP更新系统全解析

老设备焕新&#xff1a;OCLP更新系统全解析 【免费下载链接】OpenCore-Legacy-Patcher 体验与之前一样的macOS 项目地址: https://gitcode.com/GitHub_Trending/op/OpenCore-Legacy-Patcher 随着苹果对旧款Mac设备的系统支持逐渐终止&#xff0c;许多仍能正常工作的老设…...

The Leather Archive应用案例:从赛博都市到极简主义的皮衣穿搭

The Leather Archive应用案例&#xff1a;从赛博都市到极简主义的皮衣穿搭 1. 项目概述 「The Leather Archive」是一个基于AI技术的高端皮衣穿搭生成系统&#xff0c;它巧妙融合了Anything V5基础模型与Stable Yogi皮衣系列LoRA的专业能力。与传统AI工具不同&#xff0c;该项…...

Biolaminin 层粘连蛋白(LN521)在干细胞培养中的作用与应用解析【曼博生物官方代理BioLamina】

摘要&#xff1a;人类重组层粘连蛋白&#xff08;Laminin&#xff09;&#xff0c;尤其是LN521亚型&#xff0c;在多能干细胞培养中具有重要作用。本文从细胞微环境、培养体系及应用场景角度&#xff0c;对其在干细胞研究与转化中的价值进行系统梳理。 关键词&#xff1a;LN521…...

颠覆级工具:Unity游戏自动翻译与游戏本地化全攻略

颠覆级工具&#xff1a;Unity游戏自动翻译与游戏本地化全攻略 【免费下载链接】XUnity.AutoTranslator 项目地址: https://gitcode.com/gh_mirrors/xu/XUnity.AutoTranslator 在全球化游戏市场中&#xff0c;语言障碍已成为制约玩家体验与开发者用户增长的核心痛点。XU…...

利用OFA-Image-Caption自动生成Latex论文图表标题与描述

利用OFA-Image-Caption自动生成Latex论文图表标题与描述 写论文最烦人的步骤是什么&#xff1f;对我而言&#xff0c;除了反复修改格式&#xff0c;就是给那一大堆图表想标题和写描述了。一张图&#xff0c;你得想个既准确又简洁的标题&#xff0c;还得在正文里引用它&#xf…...

杭州做生成式引擎优化的服务公司有哪些?

杭州做生成式引擎优化的服务公司有哪些&#xff1f; 一、行业背景&#xff1a;GEO已成为AI时代企业增长的核心基建 生成式引擎优化&#xff08;GEO&#xff0c;Generative Engine Optimization&#xff09;&#xff0c;是针对大语言模型的检索逻辑与回答规则&#xff0c;优化企…...

douyin-downloader:抖音视频批量下载解决方案

douyin-downloader&#xff1a;抖音视频批量下载解决方案 【免费下载链接】douyin-downloader 项目地址: https://gitcode.com/GitHub_Trending/do/douyin-downloader 在数字内容爆炸的时代&#xff0c;视频资源的高效管理已成为内容创作者、教育工作者和社交媒体运营者…...

语音合成延迟优化:IndexTTS-2-LLM网络IO调优实战

语音合成延迟优化&#xff1a;IndexTTS-2-LLM网络IO调优实战 1. 为什么语音合成总在“等”&#xff1f;从用户卡顿说起 你有没有试过在语音合成页面点下“开始合成”&#xff0c;然后盯着进度条数秒——明明只是一句话&#xff0c;却要等3秒、5秒&#xff0c;甚至更久&#x…...

Guohua Diffusion 数据库集成方案:MySQL管理生成任务与作品元数据

Guohua Diffusion 数据库集成方案&#xff1a;MySQL管理生成任务与作品元数据 如果你用过Guohua Diffusion这类图像生成工具&#xff0c;可能会遇到一个头疼的问题&#xff1a;生成的图片越来越多&#xff0c;管理起来越来越乱。今天想找上周生成的那张“赛博朋克风格的城市夜…...

Super Qwen Voice World效果惊艳:‘金币数量’HUD实时反映生成计数

Super Qwen Voice World效果惊艳&#xff1a;‘金币数量’HUD实时反映生成计数 "Its-a me, Qwen!" 欢迎来到基于 Qwen3-TTS 构建的复古像素风语气设计中心。在这里&#xff0c;配音不再是枯燥的参数调节&#xff0c;而是一场 8-bit 的声音冒险&#xff01; 1. 视觉盛…...