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

动态规划算法深度解析：0-1背包问题（含完整流程）

news 来源：原创 2025/8/21 8:46:23

简介：

0-1背包问题是经典的组合优化问题：给定一组物品（每个物品有重量和价值），在背包容量限制下选择物品装入背包，要求总价值最大化且每个物品不可重复选取。

动态规划核心思想

通过构建二维状态表dp[i][j]，记录前i个物品在容量j时的最大价值，通过状态转移方程逐步推导最优解，避免重复计算子问题。

问题建模与参数定义

static final Integer N = 4;       // 物品数量
static final Integer W = 5;       // 背包容量
Integer[] w = {0,1,2,3,4};        // 物品重量数组（索引0占位）
Integer[] v = {0,2,4,5,6};        // 物品价值数组
private Integer[][] table = new Integer[N+1][W+1]; // DP状态表

代码执行全流程解析

1. 初始化阶段 `init()`

for(int i=0;i<=N;i++) {for(int j=0;j<=W;j++) {table[i][j]=0;}
}

🔍 执行过程：

创建(N+1)行×(W+1)列的二维数组
初始化边界条件：
- table[0][j] = 0（无物品可装）
- table[i][0] = 0（无容量可用）

┌───────────────┐
│  Start Init  │
└───────┬───────┘│
┌───────▼───────┐
│ i=0 to N     │
├───────┬───────┤
│ j=0 to W     │
├───────▼───────┤
│ table[i][j]=0 │
└───────┬───────┘│
┌───────▼───────┐
│ End Init      │
└───────────────┘

2. 动态规划核心 `dynamics()`

for(int i=1;i<=N;i++) {          // 物品维度for(int j=1;j<=W;j++) {      // 容量维度// 不选当前物品table[i][j] = table[i-1][j]; // 选当前物品（需容量足够）if(j >= w[i]) {table[i][j] = max(table[i][j], table[i-1][j-w[i]] + v[i]);}}
}

📊 状态转移矩阵演变：

迭代过程示例（i=2时）：容量 j | 0 1 2 3 4 5
i=0     | 0 0 0 0 0 0
i=1     | 0 2 2 2 2 2 
i=2     | 0 2 max(2,2+4)=6 ...

完整流程图与时序图

系统级流程图

在这里插入图片描述

时序图

复杂度深度分析

时间复杂度：

双重循环：O(N*W) = 4×5 = 20次核心计算
计算过程：

Σ(i=1→4) Σ(j=1→5) [1次比较 + 1次查询] = 4×5×2 = 40次操作

空间复杂度：

二维数组存储：O(N*W) = 5×6 = 30个存储单元
空间消耗分解：

基础类型Integer × 30 = 30×4 bytes = 120 bytes

完整代码

public class Knapsack {/** 假设有背包中可以最多可以装4个产品；背包承受的最大容量为5，求该背包最大的价值为多少* N：为物品数量* W：为背包容量* w[]:表示每一个产品容量* v[]:表示每一个产品的价值** */static final Integer N =4;static final Integer W= 5;Integer[] w =new Integer[]{0,1,2,3,4};Integer[] v= new  Integer[]{0,2,4,5,6};private Integer[][] table = new  Integer[N+1][W+1];void  init(){for(int i=0;i<=N;i++){for(int j=0;j<=W;j++){table[i][j]=0;}}}void print(){for(int i=0;i<=N;i++){for(int j=0;j<=W;j++){System.out.print(table[i][j]+"   ");}System.out.println();}}void dynamics(){for(int i=1;i<=N;i++){for(int j=1;j<=W;j++){table[i][j]=table[i-1][j]; // 不选第i个物品if(j>=w[i]){// 选第i个物品table[i][j]=max(table[i][j],table[i-1][j-w[i]]+v[i]);}}}}// 判断大小的方法Integer max(Integer value1,Integer value2){return value1>value2?value1:value2;}public static void main(String[] args) {Knapsack k=new Knapsack();k.init();k.dynamics();k.print();}
}

结果截图：

扩展解法对比

1. 回溯法（决策树实现）

int backtrack(int i, int currentW, int currentV) {if(i > N) return currentV;if(currentW + w[i] > W) {return backtrack(i+1, currentW, currentV);}return max(backtrack(i+1, currentW, currentV),backtrack(i+1, currentW + w[i], currentV + v[i]));
}

⚠️ 问题规模达20时计算量超百万次

2. 空间优化DP（滚动数组）

int[] dp = new int[W+1];
for(int i=1; i<=N; i++){for(int j=W; j>=w[i]; j--){ // 逆序更新dp[j] = Math.max(dp[j], dp[j-w[i]] + v[i]);}
}

🔧 优势：空间复杂度降为O(W) = 6 units

3. 分支限界法（优先队列实现）

from queue import PriorityQueueclass Node:def __init__(self, level, weight, value, bound):self.level = levelself.weight = weightself.value = valueself.bound = bounddef bound(node):# 计算剩余物品的最大可能价值...

算法选择策略

方法	适用场景	时间复杂度	空间复杂度
标准动态规划	中小规模精确计算	O(N*W)	O(N*W)
空间优化DP	大规模数据处理	O(N*W)	O(W)
回溯法	物品数<20	O(2^N)	O(N)
分支限界法	需要快速近似解	O(2^N)	O(2^N)

完整代码执行结果

0   0   0   0   0   0   
0   2   2   2   2   2   
0   2   4   6   6   6   
0   2   4   6   7   9   
0   2   4   6   7   9

最终最大价值为 9，通过物品选择（2+3号物品：重量2+3=5，价值4+5=9）实现

动态规划算法深度解析：0-1背包问题（含完整流程）

简介： 0-1背包问题是经典的组合优化问题：给定一组物品（每个物品有重量和价值），在背包容量限制下选择物品装入背包，要求总价值最大化且每个物品不可重复选取。动态规划核心思想通过构建二维状态表dp[i]…...

编程日记 2025/8/21 8:46:23

QML面试笔记--UI设计篇04交互控件

1. QML中常用交互控件 1.1. Button1.2. Slider1.3. ProgressBar1.4. TextField1.5. TextArea1.6. ComboBox1.7. CheckBox1.8. RadioButton1.9. Menu1.10. Dialog 1. QML中常用交互控件在万物互联的智能时代，QML凭借其‌声明式语法‌和‌跨平台能力‌&#xff0c…...

编程日记 2025/8/20 4:21:20

【数学】线性代数（Python）

参考：https://aibydoing.com/notebooks/appendix01-01-linear-algebra-with-python 目录矩阵的定义矩阵的运算矩阵的属性矩阵的分解矩阵的本质遗留问题矩阵的定义通过数组的维度来区分向量（1 维数组）、矩阵（2 维数组&#xff0…...

编程日记 2025/8/21 4:37:03

ragflow开启https访问:添加证书后,使用浏览器还是有警告,如何解决?

如果在 Windows 系统中安装了 PEM 证书（使用方法一通过证书管理器 MMC 导入），但浏览器仍然提示安全警告，可能有以下几个原因及解决方法： 1. 证书未正确安装到受信任的存储位置问题：如果证书被导入到错误的存储位置（如“个人”而非“受信任的根证书颁发机构”），浏览器…...

编程日记 2025/8/21 9:25:47

devServer: {host: 0.0.0.0,port: port,open: true,before(app) {app.use((req, res, next) > {// console.log(原始地址:, req.originalUrl) // 原始地址，如 /api/some-api/xxxxxnext()})},proxy: {[process.env.VUE_APP_BASE_API]: {target: http://192.168.50…...

编程日记 2025/8/22 4:50:56

【八股文】http1.0和1.1的区别

http1.0默认使用短连接，每次请求都需要建立TCP连接（三次握手），响应完成后立即关闭连接，导致资源浪费和延迟增加。支持通过Connection：Keep-alive 手动开启长连接，但需客户端和服务端显式协商 …...

编程日记 2025/8/20 16:05:03

【Prompt实战】邮件分类专家

本文原创作者：姚瑞南 AI-agent 大模型运营专家，先后任职于美团、猎聘等中大厂AI训练专家和智能运营专家岗；多年人工智能行业智能产品运营及大模型落地经验，拥有AI外呼方向国家专利与PMP项目管理证书。（转载需经授权&am…...

编程日记 2025/8/19 3:31:20

K8S核心技术点

Pod，Service和Deployment的关系 Pod：Kubernetes 中最小的部署单元，用于运行容器化应用。 Service：提供服务发现和负载均衡，为 Pod 提供稳定的网络端点，ClusterIP，NodePort，LoadBala…...

编程日记 2025/8/21 5:33:12

Python手写“随机森林”解决鸢尾花数据集分类问题

Python使用“随机森林”解决鸢尾花数据集分类问题任务描述解题1. 导入必要的库2. 数据采样函数 sample3. 设置随机种子和超参数4. 定义随机森林类 random_forest5. 加载数据集并划分训练集和测试集6. 创建并训练随机森林模型7. 进行预测并计算准确率代码任务描述您的任务是…...

编程日记 2025/8/21 16:23:07

Python 字典和集合（泛映射类型）

本章内容的大纲如下： 常见的字典方法如何处理查找不到的键标准库中 dict 类型的变种set 和 frozenset 类型散列表的工作原理散列表带来的潜在影响（什么样的数据类型可作为键、不可预知的顺序，等等） 泛映射类型 collections.…...

编程日记 2025/8/20 13:03:35

CrystalDiskInfo电脑硬盘监控工具 v9.6.0中文绿色便携版

前言 CrystalDiskInfo是一个不用花钱的硬盘小帮手软件，它可以帮你看看你的电脑硬盘工作得怎么样，健不健康。这个软件能显示硬盘的温度高不高、还有多少地方没用、传输东西快不快等等好多信息。用了它，你就能很容易地知道硬盘现在是什么情况&…...

编程日记 2025/8/20 7:43:34

rqlite：一个基于SQLite构建的分布式数据库

今天给大家介绍一个基于 SQLite 构建的轻量级分布式关系型数据库：rqlite。 rqlite 基于 Raft 协议，结合了 SQLite 的简洁性以及高可用分布式系统的稳健性，对开发者友好，操作极其简便，其核心设计理念是以最低的复杂度实…...

编程日记 2025/8/22 4:50:23

网络1 网络设备

计算机网络设备集线器： 易发生阻塞：所有端口共享一条带宽，两个端口发生传输时，其他端口若想传输数据给这两个端口，需等待这两个端口传输数据完毕。端口数量限制：10M带宽下可用15口。15口共享10Md带宽集线…...

编程日记 2025/8/21 19:28:21

mybatis 某些特殊的 ORA-00979:not a GROUP BY expression

打印的日志sql执行都是正常的但是就是报ORA-00979: not a GROUP BY expression 可能是 GROUP BY中不能使用动态参数或特殊方法使用硬编码可以解决问题 <if test"statisticsInVo.timeTypeSql!null and statisticsInVo.timeTypeSql yyyy">TO_CHAR(CARD_T…...

编程日记 2025/8/21 18:35:48

基于OpenCV的图像处理程序设计实践

一.安装OpenCV3.x # 安装依赖 sudo apt update sudo apt install build-essential cmake git libgtk2.0-dev pkg-config libavcodec-dev libavformat-dev libswscale-dev# 下载OpenCV源码 git clone https://github.com/opencv/opencv.git -b 3.4 cd opencv mkdir build &…...

编程日记 2025/8/21 8:26:25

DeepSeek 全套汇总资料pdf免费下载（最新更新8篇）

DeepSeek 全套汇总资料pdf目前仍然在持续更新中，今天更新了8篇，合计的汇总都在这里了，有需要的朋友可以直接去下载了。后续更新请关注文章：DeepSeek 全套汇总资料pdf免费下载（持续更新） _ 潘子夜个人博客…...

编程日记 2025/8/17 4:55:53

前端面试题（六）：HTTP和HTTPS的区别以及他们如何保障数据安全

HTTP（HyperText Transfer Protocol）和HTTPS（HyperText Transfer Protocol Secure）都是用于在互联网上传输数据的协议，但它们之间有一个重要的区别：安全性。 1. HTTP（超文本传输协议&#xff09…...

编程日记 2025/8/18 0:09:03

Buffer Pool 的核心作用与工作机制

Buffer Pool 的核心作用与工作机制 1. Buffer Pool 是什么？ Buffer Pool 是 InnoDB 存储引擎的核心内存区域，用于缓存磁盘中的数据页。作用：通过内存缓存减少直接磁盘 I/O，加速数据库的读写操作。默认大小：通常设…...

编程日记 2025/8/22 2:09:13

使用uglifyjs对静态引入的js文件进行压缩

前言因为有时候js文件没有npm包，或者需要修改，只能引入静态的js，那么这个时候就可以对js进行压缩了。我其实想通过vite、webpack等插件进行压缩的，可是他都不能定位到public目录下面的文件，所以我只能自己压缩了。编…...

编程日记 2025/8/17 13:46:08

Vue 3 的＜Teleport＞功能与用法

Vue 3 的 <Teleport> 功能与用法 1. 基本用法 <Teleport> 是 Vue 3 的一个内置组件，允许将组件的内容渲染到 DOM 中的任意位置，而不改变其逻辑结构。以下是基本用法： 定义目标 DOM 元素：<div id"teleport-…...

编程日记 2025/8/21 1:38:14

2025 年江苏交安安全员考试：借助本地培训资源提升能力

江苏拥有丰富的教育和培训资源，为交安安全员备考提供了有力支持。考生可关注本地专业培训机构开设的交安安全员培训课程，这些课程往往由经验丰富的讲师授课，他们熟悉本地考试特点和行业实际需求。课程内容不仅涵盖考试大纲的知识点&#xff0…...

编程日记 2025/8/22 4:50:57

Umi Max 和 Ant Design Pro 的区别

1、前言： Ant Design Pro Umi Max Umi Max 和 Ant Design Pro 其实关系很紧密，但用途不同、定位不同。我们一起来搞清楚它们的区别、联系、使用场景👇 2、一句话总结名称作用Umi Max是现代前端框架，用来构建中后台项目&#x…...

编程日记 2025/8/21 20:09:19

《 Scikit-learn与MySQL的深度协同：构建智能数据生态系统的架构哲学》

在机器学习工程实践中，数据存储与模型训练的割裂始终是制约算法效能的关键瓶颈。Scikit-learn作为经典机器学习库，其与MySQL的深度协同并非简单的数据管道连接，而是构建了一个具备自组织能力的智能数据生态系统。这种集成突破了传统ETL流程的…...

编程日记 2025/8/19 2:05:20

无公网实体服务器加装多个操作系统供多个用户互不打扰使用_part1

背景介绍因笔者业务需求，入手了一个实体服务器，但为了避免出现在一个操作系统中搭建编程环境后有许多相关的进程和服务，拖慢日常的使用，也能让其他人短期使用，更好的利用服务器的性能，让服务器专注于“什…...

编程日记 2025/8/21 2:55:49

C#调用Lua方法1+C#调用Lua方法2,3

xLua中Lua调用C#代码原因：C#实现的系统，因为Lua可以调用，所以完全可以换成Lua实现，因为Lua可以即时更改，即时运行，所以游戏的代码逻辑就可以随时更改。实现和C#相同效果的系统，如何实现&#…...

编程日记 2025/8/21 7:56:59

浅层神经网络：从数学原理到实战应用的全面解析

浅层神经网络：从数学原理到实战应用的全面解析前些天发现了一个巨牛的人工智能学习网站，通俗易懂，风趣幽默，可以分享一下给大家。点击跳转到网站。 https://www.captainbed.cn/ccc 一、神经网络演进简史：浅层网络的奠…...

编程日记 2025/8/20 8:16:19

【深度学习:理论篇】--Pytorch基础入门

目录 1.Pytorch--安装 2.Pytorch--张量 3.Pytorch--定义 4.Pytorch--运算 4.1.Tensor数据类型 4.2.Tensor创建 4.3.Tensor运算 4.4.Tensor--Numpy转换 4.5.Tensor--CUDA（GPU） 5.Pytorch--自动微分 （autograd） 5.1.back…...

编程日记 2025/8/21 23:39:34

C++中数组的概念

文章目录一、数组的定义二、什么是一维数组？2.1 一维数组的声明2.2 一维数组的初始化2.3 一维数组的使用三、什么是一维数组的数组名？四、一维数组与指针的关系五、数组指针和指针数组的区别5.1 指针数组（array of pointers）5.2…...

编程日记 2025/8/17 22:05:20

996引擎-源码学习：Cocos2d-Lua 的 class(classname, ...)

996引擎-源码学习：Cocos2d-Lua 的 class（classname, ...）一、核心方法调用顺序用户调用入口完整调用链二、__create 工厂方法的三种情形情形1：父类为函数（自定义工厂）情形2：父类为Cocos原生类情形3：父类为普通Lua表三、方法职责与内存管理对照表四、正确使用示例示例1…...

编程日记 2025/8/21 4:30:38

@linux系统SSL证书转换(Openssl转换PFX)

在Linux中，你可以使用OpenSSL工具将PFX/P12格式的证书转换为单独的CRT（证书）、KEY（私钥）文件以及提取证书链 1. 提取私钥文件(.key) openssl pkcs12 -in your_certificate.pfx -nocerts -out private.key -nodes系统会…...

编程日记 2025/8/21 22:31:19

flask返回json或者中文字符串不要编码

在 Flask 中返回中文字符串时，如果希望浏览器直接显示中文（而非编码后的 Unicode 转义字符如 \uXXXX），需确保以下两点：正确设置 HTTP 响应的字符集（如 utf-8）。避免 Flask 默认的 JSON 序列化转义中文字符。以下是具体实现方法：方法 1：直接返回纯文本（非 JSON） …...

编程日记 2025/8/20 21:30:45

打造船岸“5G+AI”智能慧眼智驱力赋能客船数智管理

项目介绍船舶在航行、作业过程中有着严格的规范要求，但在实际航行与作业中往往会因为人为的疏忽，发生事故，导致人员重大伤亡和财产损失； 为推动安全治理模式向事前预防转型，实现不安全状态和行为智能预警&#xff0c…...

编程日记 2025/8/17 23:21:04

【Proteus仿真】【32单片机-A007】PT100热敏温度检测系统设计

目录一、主要功能二、使用步骤三、硬件资源四、软件设计五、实验现象联系作者一、主要功能 1、LCD1602显示当前检测的温度值以及温度阈值 2、超过上限温度，降温模块启动 3、PT100热敏电阻测量-60C-135C 4、按键设置温度阈值 5、超过阈值&#xff0…...

编程日记 2025/8/21 3:53:56

MPDrive：利用基于标记的提示学习提高自动驾驶的空间理解能力

25年4月来自南方科技大学、百度、英国 KCL和琶洲实验室（广东 AI 和数字经济实验室）的论文“MPDrive: Improving Spatial Understanding with Marker-Based Prompt Learning for Autonomous Driving”。自动驾驶视觉问答（AD-VQA）…...

编程日记 2025/8/20 20:18:42

PhotoShop学习08

1.应用滤镜 PhotoShop提供了很多滤镜，借助滤镜可以打造很多有趣的效果。滤镜可以通过点击菜单栏的滤镜，并选择滤镜库进入滤镜调整界面。进入到滤镜库后，左侧是实时进行预览的图片，右侧可以选择滤镜效果，最右边可以调…...

编程日记 2025/8/21 1:37:53

Photoshop2025最新版v26超详细图文安装教程(附安装包)

前言 Photoshop是一款基于位图的图像处理软件，专注于对已有图像的编辑、修复、合成及特效制作。其核心功能包括图层管理、色彩校正、选区工具、滤镜效果等，支持多种颜色模型（如RGB、CMYK、CIELAB）和文件格式（如.PSD、…...

编程日记 2025/8/21 12:09:29

Plusar集群搭建-Ubuntu20.04-Winterm

1 背景已经部署了Pulsar集群在生产上，新项目需要用到Pulsar。对Pulsar不熟，故搭建练手。环境：Windows10vmwareUbuntu20.04，ssh工具使用的Winterm。使用的是root账户，ubuntu防火墙都ufw disable了。 2 参考文档集…...

编程日记 2025/8/19 15:50:19

Qt与C++数据类型转换

本文深入探讨Qt与C中相似但不同的数据类型处理技巧。一、QString与std::string的相互转换 1. QString → std::string 方法1：使用toStdString()（推荐） QString qstr "你好，Qt世界"; std::string str qstr.toStdS…...

编程日记 2025/8/20 10:06:15

Excel处理控件Aspose.Cells指南：如何查看、编辑和删除 Excel 元数据

本文是如何使用Aspose.Cells的在线工具和编码解决方案查看、编辑和删除 Excel 元数据的综合指南。无论您是寻找快速Excel 元数据查看器的普通用户，还是寻求强大的Excel 元数据编辑器的开发人员，本指南都能满足您的需求。您可以选择使用简单的在线转换器来…...

编程日记 2025/8/22 2:21:04

Rust 在汽车 MCU 编程中的进展及安全特性剖析

在当今汽车行业，软件定义汽车的趋势正深刻改变着汽车的设计与用户体验。随着汽车电子系统复杂性的不断提升，对汽车微控制器（MCU）编程的安全性、可靠性和效率提出了更高要求。Rust 作为一种新兴的编程语言，凭借其独特的…...

编程日记 2025/8/21 7:16:53

Pytorch 第十四回：神经网络编码器——变分自动编解码器

Pytorch 第十四回：神经网络编码器——变分自动编解码器本次开启深度学习第十四回，基于Pytorch的神经网络编码器。本回分享VAE变分自动编码器。在本回中，通过minist数据集来分享如何建立一个变分自动编码器。接下来给大家分享具体思路。本次…...

编程日记 2025/8/22 2:27:39

hive排序函数

在 Hive 中，排序可以通过几种不同的方法来实现，通常依赖于 ORDER BY 或 SORT BY 等函数。这里简要介绍这几种排序方法： 1. ORDER BY ORDER BY 用于对结果集进行全局排序。它会将所有数据加载到一个节点进行排序，因此可能会导致性能问题，尤其是在数据量很大的时候。语法…...

编程日记 2025/8/20 7:26:56