算法笔记:0-1背包问题

 

n个商品组成集合O,每个商品有两个属性vi(体积)和pi(价格),背包容量为C。

求解一个商品子集S,令

优化目标 max\sum_{i \in S} p_i

\sum_{i \in S} v_i \leq C

1. 枚举所有商品组合

共2^n - 1种情况

2. 递归求解

KnapsackSR(h, i, c):在第h个到第i个商品中,容量为c时的最优解

P1:选择商品i

P2:不选择商品i

取二者最大值P = max{P1+pi, P2}

3. 带备忘递归

4.  动态规划

 

 时间复杂度 O(n*C)

 

最优子结构性质:

(1)问题的最优解由相关子问题最优解组合而成

(2)子问题可以独立求解

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/150558.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

VScode配置Jupyter

环境 安装步骤 1、插件安装 2、更改pip加速源 pip config set global.index-url https://pypi.tuna.tsinghua.edu.cn/simple 参考:vscode python配置pip源 ​​​​​​​ 【Python学习】Day-00 Python安装、VScode安装、pip命令、镜像源配置、虚拟环境 3、建…

怎么通过docker/portainer部署vue项目

这篇文章分享一下如何通过docker将vue项目打包成镜像文件,并使用打包的镜像在docker/portainer上部署运行,写这篇文章参考了vue-cli和docker的官方文档。 首先,阅读vue-cli关于docker部署的说明,上面提供了关键的几个步骤。 从上面…

体会jdk17对于空指针的增强

jdk17 // 可以清楚的看出来a.b.c.num中由于c是空指针,所以导致异常 jdk11 // 只报第6行空指针了,但是因为哪个变量,不知道

Spring注册Bean系列--方法5:@Import+ImportBeanDefinitionRegistrar

原文网址:Spring注册Bean系列--方法5:ImportImportBeanDefinitionRegistrar_IT利刃出鞘的博客-CSDN博客 简介 本文介绍Spring注册Bean的方法:ImportImportBeanDefinitionRegistrar。 注册Bean的方法我写了一个系列,见&#xff…

14:00面试,14:06就出来了,这问的过于变态了。。。

前言 刚从小厂出来,没想到在另一家公司我又寄了。 在这家公司上班,每天都要加班,但看在钱给的比较多的份上,也就不太计较了。但万万没想到9月一纸通知,所有人不准加班了,不仅加班费没有了,薪资…

秒验:可以自定义UI的一键登录服务

一键登录如今成为越来越多移动应用的首选,但千篇一律的登陆界面在引发用户担忧其安全性的同时,也容易让用户在不同APP切换时产生误解。因此,由国内知名移动应用开发服务商MobTech打造的一键登录工具——秒验,通过允许开发者自定义…

Qt之QDial(表盘)

简介 QDial类提供了一个四舍五入的范围控制&#xff08;如速度计或电位计&#xff09;&#xff0c;非常适合需要循环计数的情况&#xff0c;例如角度等。 头文件&#xff1a;#include <QDial> qmake&#xff1a;QT widgets 继承&#xff1a;QAbstractSlider …

FPGA设计时序约束三、设置时钟组set_clock_groups

目录 一、背景 二、时钟间关系 2.1 时钟关系分类 2.2 时钟关系查看 三、异步时钟组 3.1 优先级 3.2 使用格式 3.3 asynchronous和exclusive 3.4 结果示例 四、参考资料 一、背景 Vivado中时序分析工具默认会分析设计中所有时钟相关的时序路径&#xff0c;除非时序约束…

Flink学习笔记(一):Flink重要概念和原理

文章目录 1、Flink 介绍2、Flink 概述3、Flink 组件介绍3.1、Deploy 物理部署层3.2、Runtime 核心层3.3、API&Libraries 层3.4、扩展库 4、Flink 四大基石4.1、Checkpoint4.2、State4.3、Time4.4、Window 5、Flink 的应用场景5.1、Event-driven Applications【事件驱动】5.…

docker数据管理和网络通信

docker数据管理 管理 Docker 容器中数据主要有两种方式&#xff1a; 数据卷&#xff08;Data Volumes&#xff09;和数据卷容器&#xff08;DataVolumes Containers&#xff09;。 1&#xff0e;数据卷 数据卷是一个供容器使用的特殊目录&#xff0c;位于容器中。可将宿主机…

轻量级MobileSAM:比FastSAM快4倍,处理一张图像仅需10ms(附源代码)

论文地址&#xff1a;https://arxiv.org/pdf/2306.14289.pdf 代码地址&#xff1a;https://github.com/ChaoningZhang/MobileSAM 一、概要简介 SAM是一种prompt-guided的视觉基础模型&#xff0c;用于从其背景中剪切出感兴趣的对象。自Meta研究团队发布SA项目以来&#xff0c…

浅析如何在抖音快速通过新手期并积累粉丝

抖音是一款非常受欢迎的短视频分享平台&#xff0c;它提供了一个快速成名和积累粉丝的机会。对于新手来说&#xff0c;通过四川不若与众总结的以下几个步骤可以帮助你快速通过抖音的新手期。 首先&#xff0c;确定你的内容定位。在抖音上&#xff0c;有各种各样的内容类型&…

解决报错:模块“react-redux“没有导出的成员“TypedUseSelectorHook”

在react整合typescript,redux时&#xff0c;写hook.ts时报这个错&#xff1a;模块"react-redux"没有导出的成员“TypedUseSelectorHook” 现象如下&#xff1a; 原因&#xff1a;react-redux版本太低&#xff0c;至少要升级到7.2.3以后才能包含TypedUseSelectorHook…

用 Pytorch 自己构建一个Transformer

一、说明 用pytorch自己构建一个transformer并不是难事,本篇使用pytorch随机生成五千个32位数的词向量做为源语言词表,再生成五千个32位数的词向量做为目标语言词表,让它们模拟翻译过程,transformer全部用pytorch实现,具备一定实战意义。 二、论文和概要 …

Pytorch目标分类深度学习自定义数据集训练

目录 一&#xff0c;Pytorch简介&#xff1b; 二&#xff0c;环境配置&#xff1b; 三&#xff0c;自定义数据集&#xff1b; 四&#xff0c;模型训练&#xff1b; 五&#xff0c;模型验证&#xff1b; 一&#xff0c;Pytorch简介&#xff1b; PyTorch是一个开源的Python机…

15经验模态分解及其改进程序,EMD,EEMD, CEEMDAN,三合一程序,已调试完成,替换自己数据可直接跑。

经验模态分解及其改进程序&#xff0c;EMD&#xff0c;EEMD, CEEMDAN,三合一程序&#xff0c;已调试完成&#xff0c;替换自己数据可直接跑。

Altium Designer培训 | 1 - 软件安装新建工程篇

目录 写在开头 工作环境 软件安装 心得 中英文切换 更改系统设置 快速启动AD 禁止AD收集个人信息 设置工程文件路径 不检查更新 禁止联网 防火墙的入站出站规则 新建入站规则 新建出站规则 工程的组成及创建 工程组成 创建工程 1.创建工程文件 2.创建原理图…

JavaScript系列从入门到精通系列第十九篇:JavaScript中的this关键字

文章目录 前言 一&#xff1a;什么是this 二&#xff1a;this的灵活妙用 前言 function fun(a,b){console.log(a b); }fun(1,2); 我们通过形参的形式往参数中添加了参数。浏览器也会默默的给我们传递一个参数过去&#xff0c;这个参数被称为this。传递的节点就是在调用函…

基于知识蒸馏的两阶段去雨去雪去雾模型学习记录(三)之知识测试阶段与评估模块

去雨去雾去雪算法分为两个阶段&#xff0c;分别是知识收集阶段与知识测试阶段&#xff0c;前面我们已经学习了知识收集阶段&#xff0c;了解到知识阶段的特征迁移模块&#xff08;CKT)与软损失&#xff08;SCRLoss&#xff09;,那么在知识收集阶段的主要重点便是HCRLoss(硬损失…

Unity可视化Shader工具ASE介绍——2、ASE的Shader创建和输入输出

大家好&#xff0c;我是阿赵&#xff0c;这里继续介绍Unity可视化写Shader的ASE插件的用法。上一篇介绍了ASE的安装和编辑器界面分布&#xff0c;这一篇主要是通过一个简单的例子介绍shader的创建和输入输出。 一、ASE的Shader创建 这里先选择Surface类型的Shader&#xff0c;…