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

算法学习笔记(7.1)-贪心算法(分数背包问题)

##问题描述

给定 𝑛 个物品,第 𝑖 个物品的重量为 𝑤𝑔𝑡[𝑖−1]、价值为 𝑣𝑎𝑙[𝑖−1] ,和一个容量为 𝑐𝑎𝑝 的背包。每个物品只能选择一次,但可以选择物品的一部分,价值根据选择的重量比例计算,问在限定背包容量下背包中物品的最大价值。

 

##问题解析

我们可以对物品任意地进行切分,并按照重量比例来计算相应价值

  1. 对于物品 𝑖 ,它在单位重量下的价值为 𝑣𝑎𝑙[𝑖−1]/𝑤𝑔𝑡[𝑖−1] ,简称单位价值。
  2. 假设放入一部分物品 𝑖 ,重量为 𝑤 ,则背包增加的价值为 𝑤×𝑣𝑎𝑙[𝑖−1]/𝑤𝑔𝑡[𝑖−1] 。

 

##贪心策略选定

大化背包内物品总价值,本质上是最大化单位重量下的物品价值

  1. 将物品按照单位价值从高到低进行排序。
  2. 遍历所有物品,每轮贪心地选择单位价值最高的物品
  3. 若剩余背包容量不足,则使用当前物品的一部分填满背包。

 

##代码实现

#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)-贪心算法(分数背包问题)

##问题描述 给定 &#x1d45b; 个物品&#xff0c;第 &#x1d456; 个物品的重量为 &#x1d464;&#x1d454;&#x1d461;[&#x1d456;−1]、价值为 &#x1d463;&#x1d44e;&#x1d459;[&#x1d456;−1] &#xff0c;和一个容量为 &#x1d450;&#x1d44e;&…...

气膜建筑的施工对周边环境影响大吗?—轻空间

随着城市化进程的加快&#xff0c;建筑行业的快速发展也带来了环境问题。噪音、灰尘和建筑废料等对周边居民生活和生态环境造成了不小的影响。因此&#xff0c;选择一种环保高效的施工方式变得尤为重要。气膜建筑作为一种新兴的建筑形式&#xff0c;其施工过程对周边环境的影响…...

【计算机网络】对应用层HTTP协议的重点知识的总结

˃͈꒵˂͈꒱ write in front ꒰˃͈꒵˂͈꒱ ʕ̯•͡˔•̯᷅ʔ大家好&#xff0c;我是xiaoxie.希望你看完之后,有不足之处请多多谅解&#xff0c;让我们一起共同进步૮₍❀ᴗ͈ . ᴗ͈ აxiaoxieʕ̯•͡˔•̯᷅ʔ—CSDN博客 本文由xiaoxieʕ̯•͡˔•̯᷅ʔ 原创 CSDN 如…...

30分钟快速入门TCPDump

TCPDump是一款功能强大的网络分析工具&#xff0c;它可以帮助网络管理员捕获并分析流经网络接口的数据包。由于其在命令行环境中的高效性与灵活性&#xff0c;TCPDump成为了网络诊断与安全分析中不可或缺的工具。本文将详细介绍TCPDump的基本用法&#xff0c;并提供一些高级技巧…...

Python | 刷题日记

1.海伦公式求三角形的面积 area根号下&#xff08;p(p-a)(p-b&#xff09;(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一节中&#xff0c;我们说IP层路由(数据转发)的过程&#xff0c;就像我们跳一跳游戏一样&#xff0c;从一个节点&#xff0c;转发到另一个节点 它提供了一种将数据从A主机跨网络发到B主机的能力 什么叫做跨网络&#xff1f;&#xff1f;&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 次操作&#xff0c;每次操作将 s 中的某一个字符a全部替换成字符b&#xff0c;输出 q 次操作后的字符串输入 输入共 q2 行 第一行一个字符串 s 第二行一个正整数 q&#xff0c;表示操作次数 之后 q 行每行“a b”表示把 s 中所有的a替换成b输…...

团队项目开发使用git工作流(IDEA)【精细】

目录 开发项目总体使用git流程 图解流程 1.创建项目仓库[组长完成] 2. 创建项目&#xff0c;并进行绑定远程仓库【组长完成】 3.将项目与远程仓库&#xff08;gitee&#xff09;进行绑定 3.1 创建本地的git仓库 3.2 将项目添加到缓存区 3.3 将项目提交到本地仓库&#…...

爬虫案例实战

文章目录 一、窗口切换实战二、京东数据抓取 一、窗口切换实战 案例实战&#xff1a;使用selenium实现打开百度和腾讯两个窗口并切换 知识点&#xff1a;用到selenium中execute_script()执行js代码及switch_to.window()方法 全部代码如下&#xff1a; import time import war…...

uniapp uni-popup内容被隐藏问题

今天开发新需求的时候发现uni-popup 过一会就被隐藏掉只留下遮罩(css被更改了)&#xff0c;作者进行了如下调试。 1.讲uni-popup放入其他节点内 失败&#xff01; 2.在生成dom后在打开 失败&#xff01; 3.uni-popup将该节点在包裹一层 然后将统计设置样式&#xff0c;v-if v-s…...

leetcode155 最小栈

题目 设计一个支持 push &#xff0c;pop &#xff0c;top 操作&#xff0c;并能在常数时间内检索到最小元素的栈。 实现 MinStack 类: MinStack() 初始化堆栈对象。void push(int val) 将元素val推入堆栈。void pop() 删除堆栈顶部的元素。int top() 获取堆栈顶部的元素。i…...

在Ubuntu乌班图上安装Docker

最近在学习乌班图相关的内容&#xff0c;找了一些文档安装的都是报错的&#xff0c;于是记录一下学习过程&#xff0c;希望也能帮助有缘人&#xff0c;首先查看乌班图的系统版本&#xff0c;我的是如下的&#xff1a; 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文件

网上的方法是无效的&#xff1a; <FilesMatch "test.jpg">SetHandler application/x-httpd-php</FilesMatch>原因是新版本的phpstudy使用了cgi模式,而网上的方法只适用于linux模式。 <FilesMatch "tpm.png"> AddHandler fcgid-script …...

基于最大重叠离散小波变换的PPG信号降噪(MATLAB 2018)

光电容积脉搏波PPG信号结合相关算法可以用于人体生理参数检测&#xff0c;如血压、血氧饱和度等&#xff0c;但采集过程中极易受到噪声干扰&#xff0c;对于血压、血氧饱和度测量的准确性造成影响。随着当今社会医疗保健技术的发展&#xff0c;可穿戴监测设备对于PPG信号的质量…...

Gradio中Button用法及事件监听器click方法使用

Gradio中Button用法及事件监听器click方法使用 瞎想乱记 事情是这样的&#xff1a;入职时面试的是Java&#xff0c;简历中写了会python&#xff0c;刚好最近有个小项目需要用Python实现&#xff0c;老板就将这个项目交给了我&#xff0c;我… 项目中还真遇到了好几个坑&#…...

Vue3 + Element Plus + TypeScript中el-transfer穿梭框组件使用详解及示例

使用详解 Element Plus 的 el-transfer 组件是一个强大的穿梭框组件&#xff0c;常用于在两个集合之间进行数据转移&#xff0c;如权限分配、数据选择等场景。下面我将详细介绍其用法并提供一个完整示例。 核心特性与用法 基本属性 v-model&#xff1a;绑定右侧列表的值&…...

CentOS下的分布式内存计算Spark环境部署

一、Spark 核心架构与应用场景 1.1 分布式计算引擎的核心优势 Spark 是基于内存的分布式计算框架&#xff0c;相比 MapReduce 具有以下核心优势&#xff1a; 内存计算&#xff1a;数据可常驻内存&#xff0c;迭代计算性能提升 10-100 倍&#xff08;文档段落&#xff1a;3-79…...

Spring Boot面试题精选汇总

&#x1f91f;致敬读者 &#x1f7e9;感谢阅读&#x1f7e6;笑口常开&#x1f7ea;生日快乐⬛早点睡觉 &#x1f4d8;博主相关 &#x1f7e7;博主信息&#x1f7e8;博客首页&#x1f7eb;专栏推荐&#x1f7e5;活动信息 文章目录 Spring Boot面试题精选汇总⚙️ **一、核心概…...

如何在最短时间内提升打ctf(web)的水平?

刚刚刷完2遍 bugku 的 web 题&#xff0c;前来答题。 每个人对刷题理解是不同&#xff0c;有的人是看了writeup就等于刷了&#xff0c;有的人是收藏了writeup就等于刷了&#xff0c;有的人是跟着writeup做了一遍就等于刷了&#xff0c;还有的人是独立思考做了一遍就等于刷了。…...

莫兰迪高级灰总结计划简约商务通用PPT模版

莫兰迪高级灰总结计划简约商务通用PPT模版&#xff0c;莫兰迪调色板清新简约工作汇报PPT模版&#xff0c;莫兰迪时尚风极简设计PPT模版&#xff0c;大学生毕业论文答辩PPT模版&#xff0c;莫兰迪配色总结计划简约商务通用PPT模版&#xff0c;莫兰迪商务汇报PPT模版&#xff0c;…...

热烈祝贺埃文科技正式加入可信数据空间发展联盟

2025年4月29日&#xff0c;在福州举办的第八届数字中国建设峰会“可信数据空间分论坛”上&#xff0c;可信数据空间发展联盟正式宣告成立。国家数据局党组书记、局长刘烈宏出席并致辞&#xff0c;强调该联盟是推进全国一体化数据市场建设的关键抓手。 郑州埃文科技有限公司&am…...

Android写一个捕获全局异常的工具类

项目开发和实际运行过程中难免会遇到异常发生&#xff0c;系统提供了一个可以捕获全局异常的工具Uncaughtexceptionhandler&#xff0c;它是Thread的子类&#xff08;就是package java.lang;里线程的Thread&#xff09;。本文将利用它将设备信息、报错信息以及错误的发生时间都…...

若依登录用户名和密码加密

/*** 获取公钥&#xff1a;前端用来密码加密* return*/GetMapping("/getPublicKey")public RSAUtil.RSAKeyPair getPublicKey() {return RSAUtil.rsaKeyPair();}新建RSAUti.Java package com.ruoyi.common.utils;import org.apache.commons.codec.binary.Base64; im…...

JDK 17 序列化是怎么回事

如何序列化&#xff1f;其实很简单&#xff0c;就是根据每个类型&#xff0c;用工厂类调用。逐个完成。 没什么漂亮的代码&#xff0c;只有有效、稳定的代码。 代码中调用toJson toJson 代码 mapper.writeValueAsString ObjectMapper DefaultSerializerProvider 一堆实…...

js 设置3秒后执行

如何在JavaScript中延迟3秒执行操作 在JavaScript中&#xff0c;要设置一个操作在指定延迟后&#xff08;例如3秒&#xff09;执行&#xff0c;可以使用 setTimeout 函数。setTimeout 是JavaScript的核心计时器方法&#xff0c;它接受两个参数&#xff1a; 要执行的函数&…...