当前位置: 首页 > 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;我… 项目中还真遇到了好几个坑&#…...

挑战杯推荐项目

“人工智能”创意赛 - 智能艺术创作助手&#xff1a;借助大模型技术&#xff0c;开发能根据用户输入的主题、风格等要求&#xff0c;生成绘画、音乐、文学作品等多种形式艺术创作灵感或初稿的应用&#xff0c;帮助艺术家和创意爱好者激发创意、提高创作效率。 ​ - 个性化梦境…...

【快手拥抱开源】通过快手团队开源的 KwaiCoder-AutoThink-preview 解锁大语言模型的潜力

引言&#xff1a; 在人工智能快速发展的浪潮中&#xff0c;快手Kwaipilot团队推出的 KwaiCoder-AutoThink-preview 具有里程碑意义——这是首个公开的AutoThink大语言模型&#xff08;LLM&#xff09;。该模型代表着该领域的重大突破&#xff0c;通过独特方式融合思考与非思考…...

2021-03-15 iview一些问题

1.iview 在使用tree组件时&#xff0c;发现没有set类的方法&#xff0c;只有get&#xff0c;那么要改变tree值&#xff0c;只能遍历treeData&#xff0c;递归修改treeData的checked&#xff0c;发现无法更改&#xff0c;原因在于check模式下&#xff0c;子元素的勾选状态跟父节…...

python爬虫:Newspaper3k 的详细使用(好用的新闻网站文章抓取和解析的Python库)

更多内容请见: 爬虫和逆向教程-专栏介绍和目录 文章目录 一、Newspaper3k 概述1.1 Newspaper3k 介绍1.2 主要功能1.3 典型应用场景1.4 安装二、基本用法2.2 提取单篇文章的内容2.2 处理多篇文档三、高级选项3.1 自定义配置3.2 分析文章情感四、实战案例4.1 构建新闻摘要聚合器…...

Axios请求超时重发机制

Axios 超时重新请求实现方案 在 Axios 中实现超时重新请求可以通过以下几种方式&#xff1a; 1. 使用拦截器实现自动重试 import axios from axios;// 创建axios实例 const instance axios.create();// 设置超时时间 instance.defaults.timeout 5000;// 最大重试次数 cons…...

使用 Streamlit 构建支持主流大模型与 Ollama 的轻量级统一平台

🎯 使用 Streamlit 构建支持主流大模型与 Ollama 的轻量级统一平台 📌 项目背景 随着大语言模型(LLM)的广泛应用,开发者常面临多个挑战: 各大模型(OpenAI、Claude、Gemini、Ollama)接口风格不统一;缺乏一个统一平台进行模型调用与测试;本地模型 Ollama 的集成与前…...

在Mathematica中实现Newton-Raphson迭代的收敛时间算法(一般三次多项式)

考察一般的三次多项式&#xff0c;以r为参数&#xff1a; p[z_, r_] : z^3 (r - 1) z - r; roots[r_] : z /. Solve[p[z, r] 0, z]&#xff1b; 此多项式的根为&#xff1a; 尽管看起来这个多项式是特殊的&#xff0c;其实一般的三次多项式都是可以通过线性变换化为这个形式…...

uniapp 字符包含的相关方法

在uniapp中&#xff0c;如果你想检查一个字符串是否包含另一个子字符串&#xff0c;你可以使用JavaScript中的includes()方法或者indexOf()方法。这两种方法都可以达到目的&#xff0c;但它们在处理方式和返回值上有所不同。 使用includes()方法 includes()方法用于判断一个字…...

elementUI点击浏览table所选行数据查看文档

项目场景&#xff1a; table按照要求特定的数据变成按钮可以点击 解决方案&#xff1a; <el-table-columnprop"mlname"label"名称"align"center"width"180"><template slot-scope"scope"><el-buttonv-if&qu…...

C++_哈希表

本篇文章是对C学习的哈希表部分的学习分享 相信一定会对你有所帮助~ 那咱们废话不多说&#xff0c;直接开始吧&#xff01; 一、基础概念 1. 哈希核心思想&#xff1a; 哈希函数的作用&#xff1a;通过此函数建立一个Key与存储位置之间的映射关系。理想目标&#xff1a;实现…...