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

动态规划之背包问题

在这里插入图片描述

文章目录

      • 0-1 背包问题
        • 1. 二维动态规划实现(0-1 背包):
        • 2. 一维动态规划实现(0-1 背包):
      • 完全背包问题
        • 1. 二维动态规划实现(完全背包):
        • 2. 一维动态规划实现(完全背包):
      • 对比
      • 总结:

下面是0-1背包问题和完全背包问题的一维和二维实现代码。

0-1 背包问题

1. 二维动态规划实现(0-1 背包):
def knapsack_01_2d(n, W, weights, values):dp = [[0] * (W + 1) for _ in range(n + 1)]  # dp[i][j] 表示前 i 种物品,容量为 j 时的最大价值for i in range(1, n + 1):for w in range(1, W + 1):if weights[i-1] <= w:dp[i][w] = max(dp[i-1][w], dp[i-1][w - weights[i-1]] + values[i-1])else:dp[i][w] = dp[i-1][w]return dp[n][W]  # 返回在 n 种物品、容量为 W 的背包中能获得的最大价值
2. 一维动态规划实现(0-1 背包):
def knapsack_01_1d(n, W, weights, values):dp = [0] * (W + 1)  # dp[j] 表示背包容量为 j 时的最大价值for i in range(n):for w in range(W, weights[i] - 1, -1):  # 逆序遍历,防止重复选择相同物品dp[w] = max(dp[w], dp[w - weights[i]] + values[i])return dp[W]  # 返回在容量为 W 的背包中能获得的最大价值

完全背包问题

1. 二维动态规划实现(完全背包):
def knapsack_complete_2d(n, W, weights, values):dp = [[0] * (W + 1) for _ in range(n + 1)]  # dp[i][j] 表示前 i 种物品,容量为 j 时的最大价值for i in range(1, n + 1):for w in range(1, W + 1):if weights[i-1] <= w:dp[i][w] = max(dp[i-1][w], dp[i][w - weights[i-1]] + values[i-1])else:dp[i][w] = dp[i-1][w]return dp[n][W]  # 返回在 n 种物品、容量为 W 的背包中能获得的最大价值
2. 一维动态规划实现(完全背包):
def knapsack_complete_1d(n, W, weights, values):dp = [0] * (W + 1)  # dp[j] 表示背包容量为 j 时的最大价值for i in range(n):for w in range(weights[i], W + 1):  # 顺序遍历,允许物品多次使用dp[w] = max(dp[w], dp[w - weights[i]] + values[i])return dp[W]  # 返回在容量为 W 的背包中能获得的最大价值

对比

以下是 0-1 背包完全背包 的对比表:

特性0-1 背包完全背包
物品选择每种物品最多选择一次。每种物品可以选择无限次(重复选择)。
状态转移状态转移方程: ( d p [ i ] [ j ] = max ⁡ ( d p [ i − 1 ] [ j ] , d p [ i − 1 ] [ j − w i ] + v i ) ) ( dp[i][j] = \max(dp[i-1][j], dp[i-1][j - w_i] + v_i) ) (dp[i][j]=max(dp[i1][j],dp[i1][jwi]+vi))状态转移方程: ( d p [ i ] [ j ] = max ⁡ ( d p [ i − 1 ] [ j ] , d p [ i ] [ j − w i ] + v i ) ) ( dp[i][j] = \max(dp[i-1][j], dp[i][j - w_i] + v_i) ) (dp[i][j]=max(dp[i1][j],dp[i][jwi]+vi))
背包容量每次只能选择当前容量下是否选择物品。每次可以选择物品多次,直到超过背包容量为止。
适用情况适用于每种物品只能选择一次的场景(例如:背包问题中的一个物品只能带一次)。适用于每种物品可以重复使用的场景(例如:无限库存问题)。
代码实现需要使用逆序遍历更新动态规划数组,以避免重复选择。顺序遍历更新动态规划数组,允许物品重复选择。
空间复杂度二维和一维优化后,空间复杂度均为 ( O ( n W ) ) ( O(nW) ) (O(nW)),其中 ( n ) 为物品种类数,( W ) 为背包容量。二维和一维优化后,空间复杂度均为 ( O ( n W ) ) ( O(nW) ) (O(nW)),其中 ( n ) 为物品种类数,( W ) 为背包容量。
时间复杂度( O ( n W ) O(nW) O(nW)),其中 ( n ) 为物品种类数,( W ) 为背包容量。 ( O ( n W ) ) ( O(nW)) (O(nW)),其中 ( n ) 为物品种类数,( W ) 为背包容量。

总结:

  • 0-1 背包:每种物品只能选择一次,适合每个物品数量有限的情况。
  • 完全背包:每种物品可以无限次选择,适合每个物品数量无限的情况。

两者的状态转移方程类似,但是由于背包问题的约束不同,选择物品的方式和更新动态规划数组的方法也有所不同。

相关文章:

动态规划之背包问题

文章目录 0-1 背包问题1. 二维动态规划实现&#xff08;0-1 背包&#xff09;&#xff1a;2. 一维动态规划实现&#xff08;0-1 背包&#xff09;&#xff1a; 完全背包问题1. 二维动态规划实现&#xff08;完全背包&#xff09;&#xff1a;2. 一维动态规划实现&#xff08;完…...

Linux抢占式内核:技术演进与源码解析

一、引言 Linux内核作为全球广泛使用的开源操作系统核心,其设计和实现一直是计算机科学领域的研究热点。从早期的非抢占式内核到2.6版本引入的抢占式内核,Linux在实时性和响应能力上取得了显著进步。本文将深入探讨Linux抢占式内核的引入背景、技术实现以及与非抢占式内核的…...

Rust语言进阶之文件处理:BufWriter用法实例(一百零四)

简介&#xff1a; CSDN博客专家、《Android系统多媒体进阶实战》一书作者 新书发布&#xff1a;《Android系统多媒体进阶实战》&#x1f680; 优质专栏&#xff1a; Audio工程师进阶系列【原创干货持续更新中……】&#x1f680; 优质专栏&#xff1a; 多媒体系统工程师系列【…...

EtherCAT主站IGH-- 30 -- IGH之master.h/c文件解析

EtherCAT主站IGH-- 30 -- IGH之master.h/c文件解析 0 预览一 该文件功能`master.c` 文件功能函数预览二 函数功能介绍`master.c` 中主要函数的作用1. `ec_master_init`2. `ec_master_clear`3. `ec_master_thread_start`4. `ec_master_thread_stop`5. `ec_master_enter_idle_pha…...

关于deepseek的一些普遍误读

最近deepseek成为全球最热门的话题&#xff0c;甚至没有之一&#xff0c;无论是北美&#xff0c;欧洲&#xff0c;各大IT巨头&#xff0c;各个投资机构&#xff0c;政府官员&#xff0c;乃至脱口秀演员&#xff0c;都在不断提及这个话题&#xff0c;而国内&#xff0c;自媒体也…...

刷题记录 动态规划-7: 63. 不同路径 II

题目&#xff1a;63. 不同路径 II 难度&#xff1a;中等 给定一个 m x n 的整数数组 grid。一个机器人初始位于 左上角&#xff08;即 grid[0][0]&#xff09;。机器人尝试移动到 右下角&#xff08;即 grid[m - 1][n - 1]&#xff09;。机器人每次只能向下或者向右移动一步。…...

7-2 拯救外星人

7-2 拯救外星人 你的外星人朋友不认得地球上的加减乘除符号&#xff0c;但是会算阶乘 —— 正整数 N 的阶乘记为 “N!”&#xff0c;是从 1 到 N 的连乘积。所以当他不知道“57”等于多少时&#xff0c;如果你告诉他等于“12!”&#xff0c;他就写出了“479001600”这个答案。…...

人工智能导论-第3章-知识点与学习笔记

参考教材3.2节的内容&#xff0c;介绍什么是自然演绎推理&#xff1b;解释“肯定后件”与“否定前件”两类错误的演绎推理是什么意义&#xff0c;给出具体例子加以阐述。参考教材3.3节的内容&#xff0c;介绍什么是文字&#xff08;literal&#xff09;&#xff1b;介绍什么是子…...

一个开源 GenBI AI 本地代理(确保本地数据安全),使数据驱动型团队能够与其数据进行互动,生成文本到 SQL、图表、电子表格、报告和 BI

一、GenBI AI 代理介绍&#xff08;文末提供下载&#xff09; github地址&#xff1a;https://github.com/Canner/WrenAI 本文信息图片均来源于github作者主页 在 Wren AI&#xff0c;我们的使命是通过生成式商业智能 &#xff08;GenBI&#xff09; 使组织能够无缝访问数据&…...

Java 大视界 -- Java 大数据在智能电网中的应用与发展趋势(71)

&#x1f496;亲爱的朋友们&#xff0c;热烈欢迎来到 青云交的博客&#xff01;能与诸位在此相逢&#xff0c;我倍感荣幸。在这飞速更迭的时代&#xff0c;我们都渴望一方心灵净土&#xff0c;而 我的博客 正是这样温暖的所在。这里为你呈上趣味与实用兼具的知识&#xff0c;也…...

c语言练习题【消息队列、共享内存、信号灯集】

练习1:消息队列 请使用消息队列实现2个终端之间互相聊天 #发送端 key_t key; int id;typedef struct Msgbuf{long channel;char buf[128];}msg_t;int main(int argc, const char *argv[]) {if (argc<2){printf("传入频道号\n");return 1;}keyftok("./ipc&q…...

力扣 295. 数据流的中位数

&#x1f517; https://leetcode.cn/problems/find-median-from-data-stream/ 题目 数据流中不断有数添加进来&#xff0c;add 表示添加数据&#xff0c;find 返回数据流中的中位数 思路 大根堆存储数据流中偏小的数据小根堆存储数据流中偏大的数据若当前的 num 比大根堆的…...

JavaScript原型链与继承:优化与扩展的深度探索

在 JavaScript 的世界里&#xff0c;万物皆对象&#xff0c;而每个对象都有一个与之关联的原型对象&#xff0c;这就构成了原型链的基础。原型链&#xff0c;简单来说&#xff0c;是一个由对象的原型相互连接形成的链式结构 。每个对象都有一个内部属性[[Prototype]]&#xff0…...

【建站】专栏目录

建站专栏的想法有很多&#xff0c;想写穷鬼如何快速低成本部署前后端项目让用户能访问到&#xff0c;如何将网站收录到百度&#xff0c;bing&#xff0c;google并优化seo让搜索引擎搜索到网站&#xff0c;想写如何把网站加入google广告或者接入stripe信用卡首款平台收款&#x…...

题目 1160: 出圈

题目描述 设有n个人围坐一圈并按顺时针方向从1到n编号&#xff0c;从第1个人开始进行1到m的报数&#xff0c;报数到第个m人&#xff0c;此人出圈&#xff0c;再从他的下一个人重新开始1到m的报数&#xff0c;如此进行下去直到所剩下一人为止。 输入格式 输入多行&#xff0c;每…...

Python小游戏29乒乓球

import pygame import sys # 初始化pygame pygame.init() # 屏幕大小 screen_width 800 screen_height 600 screen pygame.display.set_mode((screen_width, screen_height)) pygame.display.set_caption("打乒乓球") # 颜色定义 WHITE (255, 255, 255) BLACK (…...

力扣 【99. 恢复二叉搜索树】Java题解(二叉树的 Morris 遍历)

题目链接 Morris遍历 递归和迭代遍历&#xff0c;不管是前序中序还是后续&#xff0c;空间复杂度都是O(n)&#xff08;递归是因为隐式调用栈的开销&#xff09;。 而Morris遍历可以做到空间复杂度是O(1)。 思路就是节点的前序节点的右指针指向该节点&#xff0c;来保证可以通…...

CNN的各种知识点(一):卷积神经网络CNN通道数的理解!

卷积神经网络CNN通道数的理解&#xff01; 通道数的核心概念解析1. 通道数的本质 2. 单张灰度图的处理示例&#xff1a; 3. 批量输入的处理通道与批次的关系&#xff1a; 4. RGB三通道输入的处理计算过程&#xff1a;示例&#xff1a; 5. 通道数的实际意义6. 可视化理解(1) 单通…...

python-UnitTest框架笔记

UnitTest框架的基本使用方法 UnitTest框架介绍 框架&#xff1a;framework&#xff0c;为了解决一类事情的功能集合 UnitTest框架&#xff1a;是python自带的单元测试框架 自带的&#xff0c;可以直接使用&#xff0c;不需要格外安装 测试人员用来做自动化测试&#xff0c;作…...

书生大模型实战营3

文章目录 L0——入门岛git基础Git 是什么&#xff1f;Git 中的一些基本概念工作区、暂存区和 Git 仓库区文件状态分支主要功能 Git 平台介绍GitHubGitLabGitee Git 下载配置验证下载 Git配置 Git验证 Git配置 Git常用操作Git简易入门四部曲Git其他指令 闯关任务任务1: 破冰活动…...

在CentOS服务器上部署DeepSeek R1

在CentOS服务器上部署DeepSeek R1,并通过公网IP与其进行对话,可以按照以下步骤操作: 一、环境准备 系统要求: CentOS 8+(需支持AVX512指令集)。 硬件配置: GPU版本:NVIDIA驱动520+,CUDA 11.8+。 CPU版本:至少16核处理器,64GB内存。 存储空间:原始模型需要30GB,量…...

C++中常用的十大排序方法之4——希尔排序

成长路上不孤单&#x1f60a;&#x1f60a;&#x1f60a;&#x1f60a;&#x1f60a;&#x1f60a; 【&#x1f60a;///计算机爱好者&#x1f60a;///持续分享所学&#x1f60a;///如有需要欢迎收藏转发///&#x1f60a;】 今日分享关于C中常用的排序方法之4——希尔排序的相…...

机器学习day7

自定义数据集 使用pytorch框架实现逻辑回归并保存模型&#xff0c;然后保存模型后再加载模型进行预测&#xff0c;对预测结果计算精确度和召回率及F1分数 代码 import numpy as np import torch import torch.nn as nn import torch.optim as optimizer import matplotlib.pyp…...

【流媒体】搭建流媒体服务器

搭建Windows Nginx服务器 搭建 下载nginx工具包解压至本地&#xff0c;并在cmd窗口中切换至nginx所在的本地目录修改 conf/nginx.conf 文件&#xff0c;更改其端口号 server中的 listen的端口号从 80改为 8080&#xff0c;因为80经常被其他服务占用&#xff0c;导致无法打开 …...

(电脑版)植物大战僵尸幼儿园版本,开启你的冒险之旅!

欢迎来到植物大战僵尸中文版&#xff0c;园长Jen已准备好迎接你的挑战&#xff01;在这个充满乐趣和策略的游戏中&#xff0c;你将体验到多种游戏模式&#xff0c;每种模式都带来不同的挑战和乐趣。 游戏模式&#xff1a; 冒险模式&#xff1a;踏上刺激的冒险旅程&#xff0c;…...

民法学学习笔记(个人向) Part.2

民法学学习笔记(个人向) Part.2 民法始终在解决两个生活中的核心问题&#xff1a; 私法自治&#xff1b;交易安全&#xff1b; 3. 自然人 3.4 个体工商户、农村承包经营户 都是特殊的个体经济单位&#xff1b; 3.4.1 个体工商户 是指在法律的允许范围内&#xff0c;依法经…...

解决SetWindowCompositionAttribute使控件文本透明的问题

用以下参数调用该API&#xff0c;能实现类似Aero的模糊透明效果。 参数具体含义见 https://zhuanlan.zhihu.com/p/569258181 http://www.memotech.de/WindowComposition/Text.txt http://www.memotech.de/WindowComposition/WindowComposition.zip DWORD accent[4] { 3,0,0,0 …...

响应式编程与协程

响应式编程与协程的比较 响应式编程的弊端虚拟线程Java线程内核线程的局限性传统线程池的demo虚拟线程的demo 响应式编程的弊端 前面用了几篇文章介绍了响应式编程&#xff0c;它更多的使用少量线程实现线程间解耦和异步的作用&#xff0c;如线程的Reactor模型&#xff0c;主要…...

Altium Designer绘制原理图时画斜线的方法

第一步&#xff1a;检查设置是否正确 打开preferences->PCB Editor ->Interactive Routing->Interactive Routing Options->Restrict TO 90/45去掉勾选项&#xff0c;点击OK即可。如下图所示&#xff1a; 然后在划线时&#xff0c;按下shift空格就能够切换划线…...

Android --- CameraX讲解

预备知识 surface surfaceView SurfaceHolder surface 是什么&#xff1f; 一句话来说&#xff1a; surface是一块用于填充图像数据的内存。 surfaceView 是什么&#xff1f; 它是一个显示surface 的View。 在app中仍在 ViewHierachy 中&#xff0c;但在wms 中可以理解为…...

动态分库分表

1. 动态分库分表的核心目标 解决单库性能瓶颈&#xff1a;通过水平拆分数据&#xff0c;提升并发处理能力。 支持弹性扩展&#xff1a;在不中断服务的前提下&#xff0c;实现数据分片的动态扩容/缩容。 避免跨分片操作&#xff1a;减少跨分片查询&#xff08;如JOIN、事务&am…...

shell -c

个人博客地址&#xff1a;shell -c | 一张假钞的真实世界 shell -c {string}&#xff1a;表示命令从-c后的字符串读取。在需要使用管道或者重定向需要sudo时很有用&#xff0c;如下&#xff1a; $ sudo find ../*/exportFiles -mtime 15 -name "*" | xargs -I {} r…...

Spring Boot 2 快速教程:WebFlux处理流程(五)

WebFlux请求处理流程 下面是spring mvc的请求处理流程 具体步骤&#xff1a; 第一步&#xff1a;发起请求到前端控制器(DispatcherServlet) 第二步&#xff1a;前端控制器请求HandlerMapping查找 Handler &#xff08;可以根据xml配置、注解进行查找&#xff09; 匹配条件包括…...

10.8 LangChain Output Parsers终极指南:从JSON解析到流式处理的规范化输出实践

LangChain Output Parsers终极指南:从JSON解析到流式处理的规范化输出实践 关键词: LangChain Output Parsers、结构化输出、JSON解析、数据校验、流式处理 一、为什么需要规范化输出?大模型输出的“荒野西部”问题 原始输出的三大痛点: 格式不可控:模型可能返回纯文本、…...

G1. Yunli‘s Subarray Queries (easy version)

题目链接&#xff1a;Problem - 2009G1 - Codeforces 题目大意&#xff1a; 给你一个长度为n的整数数组a序列&#xff0c; 然后你可以操作任何次&#xff0c; 将序列里的一个数换成其他任意数字。 后有q次询问&#xff0c; 每一次询问[L, R] 在此区间里&#xff0c; 可最少进行…...

[漏洞篇]SQL注入漏洞详解

[漏洞篇]SQL注入漏洞详解 介绍 把SQL命令插入到Web表单提交或输入域名或页面请求的查询字符串&#xff0c;最终达到欺骗服务器执行恶意的SQL命令。通过构造恶意的输入&#xff0c;使数据库执行恶意命令&#xff0c;造成数据泄露或者修改内容等&#xff0c;以达到攻击的目的。…...

【apt源】RK3588 平台ubuntu20.04更换apt源

RK3588芯片使用的是aarch64架构&#xff0c;因此在Ubuntu 20.04上更换apt源时需要使用针对aarch64架构的源地址。以下是针对RK3588芯片在Ubuntu 20.04上更换apt源到清华源的正确步骤&#xff1a; 步骤一&#xff1a;打开终端 在Ubuntu 20.04中&#xff0c;按下Ctrl Alt T打…...

Maven

什么是Maven&#xff1f; Maven是一个项目管理工具&#xff0c;基于POM&#xff08;Project Object Model&#xff0c;项目对象模型&#xff09;的概念呢&#xff0c;Maven可以通过一小段描述信息来管理项目的构建&#xff0c;报告和文档的项目管理工具软件。 Maven包含了一个…...

软件工程概论试题五

一、多选 1.好的软件的基本属性包括()。 A. 效率 B. 可依赖性和信息安全性 C. 可维护性 D.可接受性 正答&#xff1a;ABCD 2.软件工程的三要素是什么()? A. 结构化 B. 工具 C.面向对象 D.数据流! E.方法 F.过程 正答&#xff1a;BEF 3.下面中英文术语对照哪些是正确的、且是属…...

Python量化交易助手:xtquant的安装与应用

Python量化交易助手&#xff1a;xtquant的安装与应用 技术背景和应用场景 在量化交易领域&#xff0c;Python因其强大的库支持和灵活性成为了许多开发者的首选语言。其中&#xff0c;xtquant 是迅投官方开发的一个Python包&#xff0c;专门用于与miniqmt通信&#xff0c;实现…...

opencv图像处理框架

一.课程简介与环境配置 二.图像基本操作 (1)计算机眼中的视觉 1)计算机眼中图像是由一块块组成&#xff0c;每一块又由很多很多个像素点组成&#xff0c;一个像素点的值是在0到255之间&#xff0c;值越大就越亮。 2)RGB表示彩色图像的三个颜色通道(红绿蓝)&#xff0c;一张…...

MotionLCM 部署笔记

目录 依赖项 humanml3d&#xff1a; sentence-t5-large 下载数据&#xff1a; 报错&#xff1a;No module named sentence_transformers 继续报错&#xff1a;from transformers.integrations import CodeCarbonCallback 解决方法&#xff1a; 推理相关 GitHub - Dai-W…...

BUUCTF_[安洵杯 2019]easy_web(preg_match绕过/MD5强碰撞绕过/代码审计)

打开靶场&#xff0c;出现下面的静态html页面&#xff0c;也没有找到什么有价值的信息。 查看页面源代码 在url里发现了img传参还有cmd 求img参数 这里先从img传参入手&#xff0c;这里我发现img传参好像是base64的样子 进行解码&#xff0c;解码之后还像是base64的样子再次进…...

LLM - 基于LM Studio本地部署DeepSeek-R1的蒸馏量化模型

文章目录 前言开发环境快速开始LM Studio简单设置模型下载开始对话 模型选择常见错误最后 前言 目前&#xff0c;受限于设备性能&#xff0c;在本地部署的基本都是DeepSeek-R1的蒸馏量化模型&#xff0c;这些蒸馏量化模型的表现可能并没有你想象的那么好。绝大部分人并不需要本…...

Intel 与 Yocto 项目的深度融合:全面解析与平台对比

在嵌入式 Linux 领域&#xff0c;Yocto 项目已成为构建定制化 Linux 发行版的事实标准&#xff0c;广泛应用于不同架构的 SoC 平台。Intel 作为 x86 架构的领导者&#xff0c;在 Yocto 生态中投入了大量资源&#xff0c;为其嵌入式处理器、FPGA 和 AI 加速硬件提供了完整的支持…...

2025-工具集合整理

科技趋势 github-rank &#x1f577;️Github China/Global User Ranking, Global Warehouse Star Ranking (Github Action is automatically updated daily). 科技爱好者周刊 制图工具 D2 D2 A modern diagram scripting language that turns text to diagrams 文档帮助 …...

快速提升网站收录:利用网站新闻发布功能

本文转自&#xff1a;百万收录网 原文链接&#xff1a;https://www.baiwanshoulu.com/63.html 利用网站新闻发布功能快速提升网站收录是一个有效的策略。以下是一些具体的建议&#xff0c;帮助你更好地利用这一功能&#xff1a; 一、保持新闻更新频率 搜索引擎尤其重视网站的…...

wxss样式模板,全局配置window

1 wxss样式模板 1.1什么是wxss 1.2 rpx 1.3 样式导入 1.4 全局样式 1.5局部样式 2 全局配置 2.1 全局配置window 2.2 window 导航栏区域...

git多人协作

目录 一、项目克隆 二、 1、进入克隆仓库设置 2、协作处理 3、冲突处理 4、多人协作分支的推送拉取删除 1、分支推送&#xff08;2种&#xff09; 2、远程分支拉取&#xff08;2种&#xff09; 3、远程分支删除 一、项目克隆 git clone 画船听雨眠/test1 (自定义的名…...

Maven全解析:从基础到精通的实战指南

概念&#xff1a; Maven 是跨平台的项目管理工具。主要服务基于 Java 平台的构建&#xff0c;依赖管理和项目信息管理项目构建&#xff1a;高度自动化&#xff0c;跨平台&#xff0c;可重用的组件&#xff0c;标准化的流程 依赖管理&#xff1a; 对第三方依赖包的管理&#xf…...