算法学习笔记(7.1)-贪心算法(分数背包问题)
##问题描述
给定 𝑛 个物品,第 𝑖 个物品的重量为 𝑤𝑔𝑡[𝑖−1]、价值为 𝑣𝑎𝑙[𝑖−1] ,和一个容量为 𝑐𝑎𝑝 的背包。每个物品只能选择一次,但可以选择物品的一部分,价值根据选择的重量比例计算,问在限定背包容量下背包中物品的最大价值。

##问题解析
我们可以对物品任意地进行切分,并按照重量比例来计算相应价值。
- 对于物品 𝑖 ,它在单位重量下的价值为 𝑣𝑎𝑙[𝑖−1]/𝑤𝑔𝑡[𝑖−1] ,简称单位价值。
- 假设放入一部分物品 𝑖 ,重量为 𝑤 ,则背包增加的价值为 𝑤×𝑣𝑎𝑙[𝑖−1]/𝑤𝑔𝑡[𝑖−1] 。

##贪心策略选定
大化背包内物品总价值,本质上是最大化单位重量下的物品价值。
- 将物品按照单位价值从高到低进行排序。
- 遍历所有物品,每轮贪心地选择单位价值最高的物品。
- 若剩余背包容量不足,则使用当前物品的一部分填满背包。

##代码实现
#python代码示例 class Item :def __init__(self,w,v):self.w = w self.v = vdef fraction_knapsack(wgt,val,cap) :items = [Item(w,v) for w,v in zip(wgt,val)]items.sort(key = lambda x : x.v / x.w,reverse=True)res = 0for item in items :if item.w <= cap :res += item.vcap -= item.welse :res += (item.v / item.w) * cap breakreturn res//c++代码示例 class Item {int w ;int v ;Item(int w,int v) : w(w),v(v){} } ;double fractionKnapsack(vector<int> &wgt,vector<int> &val,int cap) {vector<int> items ;for (int i = 0 ; i < wgt.size() ; i++){items.push_back(Item(wgt[i],val[i])) ;}sort(items.begin(),items.end(),[](Item &a,Item &b){return (double)a.v/a.w > (double)b.v/b.w ;});double res = 0 ;for (auto &item : items){if (item.w <= cap){res = res + item.v ;cap = cap - item.w ;}else{res = res + (double)(item.v/item.w) * cap ;break ; }}return res ;}
##正确性验证
单位价值更大的物品总是最优选择,贪心策略一定有效。

相关文章:
算法学习笔记(7.1)-贪心算法(分数背包问题)
##问题描述 给定 𝑛 个物品,第 𝑖 个物品的重量为 𝑤𝑔𝑡[𝑖−1]、价值为 𝑣𝑎𝑙[𝑖−1] ,和一个容量为 𝑐𝑎&…...
气膜建筑的施工对周边环境影响大吗?—轻空间
随着城市化进程的加快,建筑行业的快速发展也带来了环境问题。噪音、灰尘和建筑废料等对周边居民生活和生态环境造成了不小的影响。因此,选择一种环保高效的施工方式变得尤为重要。气膜建筑作为一种新兴的建筑形式,其施工过程对周边环境的影响…...
【计算机网络】对应用层HTTP协议的重点知识的总结
˃͈꒵˂͈꒱ write in front ꒰˃͈꒵˂͈꒱ ʕ̯•͡˔•̯᷅ʔ大家好,我是xiaoxie.希望你看完之后,有不足之处请多多谅解,让我们一起共同进步૮₍❀ᴗ͈ . ᴗ͈ აxiaoxieʕ̯•͡˔•̯᷅ʔ—CSDN博客 本文由xiaoxieʕ̯•͡˔•̯᷅ʔ 原创 CSDN 如…...
30分钟快速入门TCPDump
TCPDump是一款功能强大的网络分析工具,它可以帮助网络管理员捕获并分析流经网络接口的数据包。由于其在命令行环境中的高效性与灵活性,TCPDump成为了网络诊断与安全分析中不可或缺的工具。本文将详细介绍TCPDump的基本用法,并提供一些高级技巧…...
Python | 刷题日记
1.海伦公式求三角形的面积 area根号下(p(p-a)(p-b)(p-c)) p是周长的一半 2.随机生成一个整数 import random xrandom.randint(0,9)#随机生成0到9之间的一个数 yeval(input("please input:")) if xy:print("bingo") elif x<y:pri…...
“JS逆向 | Python爬虫 | 动态cookie如何破~”
案例目标 目标网址:aHR0cHMlM0EvL21hdGNoLnl1YW5yZW54dWUuY29tL21hdGNoLzI= 本题目标:提取全部 5 页发布日热度的值,计算所有值的加和,并提交答案 常规 JavaScript 逆向思路 JavaScript 逆向工程通常分为以下三步: 寻找入口:逆向工程的核心在于找出加密参数的生成方式。…...
十.数据链路层——MAC/ARP
IP和数据链路层之间的关系 引言 在IP一节中,我们说IP层路由(数据转发)的过程,就像我们跳一跳游戏一样,从一个节点,转发到另一个节点 它提供了一种将数据从A主机跨网络发到B主机的能力 什么叫做跨网络??&a…...
Linux主机安全可视化运维(免费方案)
本文介绍如何使用免费的主机安全软件,在自有机房或企业网络实现对Linux系统进行可视化“主机安全”管理。 一、适用对象 本文适用于个人或企业内的Linux服务器运维场景,实现免费、高效、可视化的主机安全管理。提前发现主机存在的安全风险,全方位实时监控主机运行时入侵事…...
Vite + Vue 3 前端项目实战
一、项目创建 npm install -g create-vite #安装 Vite 项目的脚手架工具 # 或者使用yarn yarn global add create-vite#创建vite项目 create-vite my-vite-project二、常用Vue项目依赖安装 npm install unplugin-auto-import unplugin-vue-components[1] 安装按需自动导入组…...
python-字符替换
[题目描述] 给出一个字符串 s 和 q 次操作,每次操作将 s 中的某一个字符a全部替换成字符b,输出 q 次操作后的字符串输入 输入共 q2 行 第一行一个字符串 s 第二行一个正整数 q,表示操作次数 之后 q 行每行“a b”表示把 s 中所有的a替换成b输…...
团队项目开发使用git工作流(IDEA)【精细】
目录 开发项目总体使用git流程 图解流程 1.创建项目仓库[组长完成] 2. 创建项目,并进行绑定远程仓库【组长完成】 3.将项目与远程仓库(gitee)进行绑定 3.1 创建本地的git仓库 3.2 将项目添加到缓存区 3.3 将项目提交到本地仓库&#…...
爬虫案例实战
文章目录 一、窗口切换实战二、京东数据抓取 一、窗口切换实战 案例实战:使用selenium实现打开百度和腾讯两个窗口并切换 知识点:用到selenium中execute_script()执行js代码及switch_to.window()方法 全部代码如下: import time import war…...
uniapp uni-popup内容被隐藏问题
今天开发新需求的时候发现uni-popup 过一会就被隐藏掉只留下遮罩(css被更改了),作者进行了如下调试。 1.讲uni-popup放入其他节点内 失败! 2.在生成dom后在打开 失败! 3.uni-popup将该节点在包裹一层 然后将统计设置样式,v-if v-s…...
leetcode155 最小栈
题目 设计一个支持 push ,pop ,top 操作,并能在常数时间内检索到最小元素的栈。 实现 MinStack 类: MinStack() 初始化堆栈对象。void push(int val) 将元素val推入堆栈。void pop() 删除堆栈顶部的元素。int top() 获取堆栈顶部的元素。i…...
在Ubuntu乌班图上安装Docker
最近在学习乌班图相关的内容,找了一些文档安装的都是报错的,于是记录一下学习过程,希望也能帮助有缘人,首先查看乌班图的系统版本,我的是如下的: cat /proc/version以下是在Ubuntu 20.04版本上安装Docker。…...
【Redis数据库百万字详解】数据持久化
文章目录 一、持久化1.1、什么是持久化1.2、持久化方式1.3、RDB优缺点1.4、AOF优缺点 二、RDB持久化触发机制2.1、手动触发2.2、自动触发 三、RDB持久化配置3.1、配置文件3.2、配置查询/设置3.3、禁用持久化3.4、RDB文件恢复 四、RDB持久化案例4.1、手动持久化4.2、自动持久化案…...
echarts legend. icon的展示
默认展示 icon展示circle圆形rect矩形roundRect圆角矩形triangle三角形diamond菱形pin水滴arrow箭头none不显示...
PHPstudy情况下上传图片马需要的.htaccess文件
网上的方法是无效的: <FilesMatch "test.jpg">SetHandler application/x-httpd-php</FilesMatch>原因是新版本的phpstudy使用了cgi模式,而网上的方法只适用于linux模式。 <FilesMatch "tpm.png"> AddHandler fcgid-script …...
基于最大重叠离散小波变换的PPG信号降噪(MATLAB 2018)
光电容积脉搏波PPG信号结合相关算法可以用于人体生理参数检测,如血压、血氧饱和度等,但采集过程中极易受到噪声干扰,对于血压、血氧饱和度测量的准确性造成影响。随着当今社会医疗保健技术的发展,可穿戴监测设备对于PPG信号的质量…...
Gradio中Button用法及事件监听器click方法使用
Gradio中Button用法及事件监听器click方法使用 瞎想乱记 事情是这样的:入职时面试的是Java,简历中写了会python,刚好最近有个小项目需要用Python实现,老板就将这个项目交给了我,我… 项目中还真遇到了好几个坑&#…...
【杂谈】-递归进化:人工智能的自我改进与监管挑战
递归进化:人工智能的自我改进与监管挑战 文章目录 递归进化:人工智能的自我改进与监管挑战1、自我改进型人工智能的崛起2、人工智能如何挑战人类监管?3、确保人工智能受控的策略4、人类在人工智能发展中的角色5、平衡自主性与控制力6、总结与…...
【第二十一章 SDIO接口(SDIO)】
第二十一章 SDIO接口 目录 第二十一章 SDIO接口(SDIO) 1 SDIO 主要功能 2 SDIO 总线拓扑 3 SDIO 功能描述 3.1 SDIO 适配器 3.2 SDIOAHB 接口 4 卡功能描述 4.1 卡识别模式 4.2 卡复位 4.3 操作电压范围确认 4.4 卡识别过程 4.5 写数据块 4.6 读数据块 4.7 数据流…...
JVM垃圾回收机制全解析
Java虚拟机(JVM)中的垃圾收集器(Garbage Collector,简称GC)是用于自动管理内存的机制。它负责识别和清除不再被程序使用的对象,从而释放内存空间,避免内存泄漏和内存溢出等问题。垃圾收集器在Ja…...
生成 Git SSH 证书
🔑 1. 生成 SSH 密钥对 在终端(Windows 使用 Git Bash,Mac/Linux 使用 Terminal)执行命令: ssh-keygen -t rsa -b 4096 -C "your_emailexample.com" 参数说明: -t rsa&#x…...
论文浅尝 | 基于判别指令微调生成式大语言模型的知识图谱补全方法(ISWC2024)
笔记整理:刘治强,浙江大学硕士生,研究方向为知识图谱表示学习,大语言模型 论文链接:http://arxiv.org/abs/2407.16127 发表会议:ISWC 2024 1. 动机 传统的知识图谱补全(KGC)模型通过…...
零基础在实践中学习网络安全-皮卡丘靶场(第九期-Unsafe Fileupload模块)(yakit方式)
本期内容并不是很难,相信大家会学的很愉快,当然对于有后端基础的朋友来说,本期内容更加容易了解,当然没有基础的也别担心,本期内容会详细解释有关内容 本期用到的软件:yakit(因为经过之前好多期…...
听写流程自动化实践,轻量级教育辅助
随着智能教育工具的发展,越来越多的传统学习方式正在被数字化、自动化所优化。听写作为语文、英语等学科中重要的基础训练形式,也迎来了更高效的解决方案。 这是一款轻量但功能强大的听写辅助工具。它是基于本地词库与可选在线语音引擎构建,…...
从“安全密码”到测试体系:Gitee Test 赋能关键领域软件质量保障
关键领域软件测试的"安全密码":Gitee Test如何破解行业痛点 在数字化浪潮席卷全球的今天,软件系统已成为国家关键领域的"神经中枢"。从国防军工到能源电力,从金融交易到交通管控,这些关乎国计民生的关键领域…...
【无标题】湖北理元理律师事务所:债务优化中的生活保障与法律平衡之道
文/法律实务观察组 在债务重组领域,专业机构的核心价值不仅在于减轻债务数字,更在于帮助债务人在履行义务的同时维持基本生活尊严。湖北理元理律师事务所的服务实践表明,合法债务优化需同步实现三重平衡: 法律刚性(债…...
Kubernetes 节点自动伸缩(Cluster Autoscaler)原理与实践
在 Kubernetes 集群中,如何在保障应用高可用的同时有效地管理资源,一直是运维人员和开发者关注的重点。随着微服务架构的普及,集群内各个服务的负载波动日趋明显,传统的手动扩缩容方式已无法满足实时性和弹性需求。 Cluster Auto…...
