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

7.2.背包DP

news 来源：原创 2025/5/14 15:58:07

背包DP

在C++中，背包动态规划（Knapsack DP） 是解决资源分配类问题的核心算法范式，尤其在处理物品选择与容量限制的组合优化问题时表现优异。以下是针对不同背包类型的详细解析与代码实现：

一、背包DP问题分类

类型	特点	经典问题场景
0-1背包	每件物品只能选0或1次	物品不可分割（如金条）
完全背包	每件物品可选无限次	硬币兑换（面额无限供应）
多重背包	每件物品最多选k次	有限库存的商品采购
分组背包	物品分组，每组选一件	课程选修（多门课选其一）

二、0-1背包问题

问题描述

给定物品重量 weights[] 和价值 values[]，背包容量 W，求能装入的最大总价值。

状态定义

基础二维DP：dp[i][w] 表示前 i 个物品在容量 w 下的最大价值
优化一维DP：dp[w] 表示容量 w 下的最大价值（空间压缩）

状态转移方程

不选第 i 件：dp[i][w] = dp[i-1][w]
选第 i 件：dp[i][w] = dp[i-1][w - weights[i]] + values[i]
综合：dp[i][w] = max(dp[i-1][w], dp[i-1][w - weights[i]] + values[i])

C++实现

// 二维DP（清晰但空间占用大）
int knapsack_01_2D(vector<int>& weights, vector<int>& values, int W) {int n = weights.size();vector<vector<int>> dp(n+1, vector<int>(W+1, 0));for (int i = 1; i <= n; ++i) {for (int w = 0; w <= W; ++w) {if (w < weights[i-1]) {dp[i][w] = dp[i-1][w];} else {dp[i][w] = max(dp[i-1][w], dp[i-1][w - weights[i-1]] + values[i-1]);}}}return dp[n][W];
}// 一维DP（空间优化，必须逆序遍历容量）
int knapsack_01_1D(vector<int>& weights, vector<int>& values, int W) {vector<int> dp(W + 1, 0);for (int i = 0; i < weights.size(); ++i) {for (int w = W; w >= weights[i]; --w) { // 逆向更新dp[w] = max(dp[w], dp[w - weights[i]] + values[i]);}}return dp[W];
}

关键点

逆序遍历容量：确保每个物品只被计算一次
索引对应：weights[i-1] 对应二维版的第 i 个物品（一维版直接 weights[i]）

三、完全背包问题

问题描述

物品可无限次选取，求装满背包的最大价值。

状态转移方程

dp[w] = max(dp[w], dp[w - weights[i]] + values[i])
（与0-1背包的唯一区别是 正序遍历容量）

C++实现

int knapsack_unbounded(vector<int>& weights, vector<int>& values, int W) {vector<int> dp(W + 1, 0);for (int i = 0; i < weights.size(); ++i) {for (int w = weights[i]; w <= W; ++w) { // 正序遍历dp[w] = max(dp[w], dp[w - weights[i]] + values[i]);}}return dp[W];
}

应用场景

零钱兑换问题（LeetCode 322）
凑满容量的最小物品数（LeetCode 279）

四、多重背包问题

问题描述

每个物品有数量限制 counts[i]，最多选 counts[i] 次。

优化方法

将多重背包转换为 0-1背包 + 二进制拆分，减少物品数量：

例如：将13个物品拆分为 1, 2, 4, 6（组合可表示1~13）

C++实现

int knapsack_multiple(vector<int>& weights, vector<int>& values, vector<int>& counts, int W) {// 二进制拆分预处理vector<int> new_weights, new_values;for (int i = 0; i < weights.size(); ++i) {int k = 1;while (counts[i] > 0) {int amount = min(k, counts[i]);new_weights.push_back(weights[i] * amount);new_values.push_back(values[i] * amount);counts[i] -= amount;k *= 2;}}// 转换为0-1背包vector<int> dp(W + 1, 0);for (int i = 0; i < new_weights.size(); ++i) {for (int w = W; w >= new_weights[i]; --w) {dp[w] = max(dp[w], dp[w - new_weights[i]] + new_values[i]);}}return dp[W];
}

五、分组背包问题

问题描述

物品被分为多组，每组只能选一个物品。

状态转移方程

dp[w] = max{ 不选该组 / 选该组第k个物品 }

C++实现

int group_knapsack(vector<vector<pair<int, int>>>& groups, int W) {vector<int> dp(W + 1, 0);for (auto& group : groups) { // 遍历每组for (int w = W; w >= 0; --w) { // 逆序遍历容量for (auto& item : group) { // 遍历组内物品int weight = item.first, value = item.second;if (w >= weight) {dp[w] = max(dp[w], dp[w - weight] + value);}}}}return dp[W];
}

六、常见问题与调试技巧

1. 初始化陷阱

要求恰好装满背包时：dp[0] = 0，其他初始化为 -INF
不要求装满时：全部初始化为 0

2. 遍历顺序总结

背包类型	容量遍历顺序	物品遍历顺序
0-1背包	逆序	先物品后容量
完全背包	正序	先物品后容量
分组背包	逆序	先组后容量再物品

3. 测试用例设计

边界测试：容量为0、物品重量为0
极端情况：所有物品重量超过容量
完全覆盖：验证状态转移的所有分支

七、典型例题与代码

1. 分割等和子集（LeetCode 416）

转化为0-1背包：找是否能凑出 sum/2

bool canPartition(vector<int>& nums) {int sum = accumulate(nums.begin(), nums.end(), 0);if (sum % 2 != 0) return false;int target = sum / 2;vector<bool> dp(target + 1, false);dp[0] = true;for (int num : nums) {for (int w = target; w >= num; --w) {dp[w] = dp[w] || dp[w - num];}}return dp[target];
}

2. 零钱兑换 II（LeetCode 518）

完全背包求组合数：

int change(int amount, vector<int>& coins) {vector<int> dp(amount + 1, 0);dp[0] = 1;for (int coin : coins) { // 先遍历物品（保证组合数）for (int w = coin; w <= amount; ++w) {dp[w] += dp[w - coin];}}return dp[amount];
}

八、性能优化进阶

滚动数组：将二维DP压缩为两个一维数组交替使用
单调队列优化：适用于特定多重背包问题
位运算优化：当价值较小时，用bitset加速状态转移

掌握背包DP的关键在于 理解物品选择逻辑与遍历顺序的关系，并通过大量练习熟悉不同变种的解题模式。建议从标准0-1背包入手，逐步扩展到更复杂的变种。

7.2.背包DP

背包DP 在C中，背包动态规划（Knapsack DP） 是解决资源分配类问题的核心算法范式，尤其在处理物品选择与容量限制的组合优化问题时表现优异。以下是针对不同背包类型的详细解析与代码实现： 一、背包DP问题分类类型特点…...

编程日记 2025/5/14 15:58:07

芝法酱学习笔记（2.6）——flink-cdc监听mysql binlog并同步数据至elastic-search和更新redis缓存

一、需求背景在有的项目中，尤其是进销存类的saas软件，一开始为了快速把产品做出来，并没有考虑缓存问题。而这类软件，有着复杂的业务逻辑。如果想在原先的代码中，添加redis缓存，改动面将非常大&#xff0c…...

编程日记 2025/5/12 20:59:20

pandas习题 071：字典元素列表构造 DataFrame

（编码题）以下有一个列表嵌套字典 data，列表中的每个字典 fields 中的列表为每行数据的值，另有一个 col 为列名，利用这两个数据构造一个 DataFrame。 data = [{fields: [2024-10-07T21:22:01, USER-A, 21, 0,...

编程日记 2025/5/7 1:39:12

FFmpeg rtmp推流直播

文章目录 rtmp协议RTMP协议组成RTMP的握手过程RTMP流的创建RTMP消息格式Chunking(Message 分块) rtmp服务器搭建Nginx服务器配置Nginx服务器 librtmp库编译推流 rtmp协议 RTMP（Real Time Messaging Protocol）是由Adobe公司基于Flash Player播放器对应的…...

编程日记 2025/5/14 15:38:04

北京门头沟区房屋轮廓shp的arcgis数据建筑物轮廓无偏移坐标测评

在IT行业中，地理信息系统（GIS）是用于处理、分析和展示地理空间数据的重要工具，而ArcGIS则是GIS领域中的一款知名软件。本文将详细解析标题和描述中提及的知识点，并结合“门头沟区建筑物数据”这一标签，深入…...

编程日记 2025/5/14 15:49:47

Verilog基础（一）：基础元素

verilog基础我先说，看了肯定会忘，但是重要的是这个过程，我们知道了概念，知道了以后在哪里查询。语法都是术，通用的概念是术。所以如果你有相关的软件编程经验，那么其实开启这个学习之旅，你会感…...

编程日记 2025/5/14 15:50:50

Games104——游戏引擎Gameplay玩法系统：基础AI

这里写目录标题寻路/导航系统NavigationWalkable AreaWaypoint NetworkGridNavigation Mesh（寻路网格）Sparse Voxel Octree Path FindingDijkstra Algorithm迪杰斯特拉算法A Star（A*算法） Path Smoothing Steering系统Crowd Simu…...

编程日记 2025/5/8 5:45:34

vue生命周期及其作用

vue生命周期及其作用 1. 生命周期总览 2. beforeCreate 我们在new Vue()时，初始化一个Vue空的实例对象，此时对象身上只有默认的声明周期函数和事件，此时data,methods都未被初始化 3. created 此时，已经完成数据观测&#xff0…...

编程日记 2025/5/14 15:05:27

数据分析师使用Kutools for Excel 插件

数据分析师使用Kutools for Excel 插件 Kutools for Excel 是一款功能强大的 Excel 插件，旨在提高 Excel 用户的工作效率，简化复杂的操作。它提供了超过 300 个增强功能，帮助用户快速完成数据管理、格式化、排序、分析等任务，特别…...

编程日记 2025/5/14 15:30:11

毫秒级响应的VoIP中的系统组合推荐

在高并发、低延迟、毫秒级响应的 VoIP 场景中，选择合适的操作系统组合至关重要。以下是针对 Ubuntu linux-lowlatency、CentOS Stream kernel-rt 和 Debian 自定义 PREEMPT_RT 的详细对比及推荐： 1. 系统组合对比特性Ubuntu linux-lowlatencyCentO…...

编程日记 2025/5/14 15:47:18

unordered_map/set的哈希封装

【C笔记】unordered_map/set的哈希封装 🔥个人主页：大白的编程日记 🔥专栏：C笔记文章目录【C笔记】unordered_map/set的哈希封装前言一. 源码及框架分析二.迭代器三.operator[]四.使用哈希表封装unordered_map/set后言前言哈…...

编程日记 2025/5/14 14:56:45

表格标签的使用

一.表格标签 1.1表格标签的作用用来显示和展示数据，不是用来布局页面的。 1.2表格的基本语法 <table> //用于定义表格标签 <tr> // table row 用于定义表格中的行，必须嵌套在<table> </table>标签中 <td>单元格内的文…...

编程日记 2025/4/9 15:52:04

python算法和数据结构刷题[5]：动态规划

动态规划（Dynamic Programming, DP）是一种算法思想，用于解决具有最优子结构的问题。它通过将大问题分解为小问题，并找到这些小问题的最优解，从而得到整个问题的最优解。动态规划与分治法相似，但区别在于动态…...

编程日记 2025/5/14 12:03:32

【cocos creator】【模拟经营】餐厅经营demo

下载：【cocos creator】模拟经营餐厅经营...

编程日记 2025/5/12 20:49:31

编程AI深度实战：给vim装上AI

系列文章： 编程AI深度实战：私有模型deep seek r1，必会ollama-CSDN博客编程AI深度实战：自己的AI，必会LangChain-CSDN博客编程AI深度实战：给vim装上AI-CSDN博客编程AI深度实战：火的编程AI&…...

编程日记 2025/5/13 7:58:04

信息学奥赛一本通 2088：【22CSPJ普及组】逻辑表达式(expr) | 洛谷 P8815 [CSP-J 2022] 逻辑表达式

【题目链接】 ybt 2088：【22CSPJ普及组】逻辑表达式(expr) 洛谷 P8815 [CSP-J 2022] 逻辑表达式【题目考点】 1. 表达式树：中缀表达式建树可以看该问题信息学奥赛一本通 1356：计算(calc) 了解中缀表达式建树过程。【解题思路】解法…...

编程日记 2025/5/13 3:19:15

Linux系统管理

文章目录一、进程与服务二、systemctl基本语法操作三、系统运行级别Linux进程运行级别查看当前运行级别修改当前运行级别四、关机重启命令一、进程与服务守护进程与服务是一个东西。二、systemctl 基本语法 systemctl start|stop|restart|status 服务名查看服务的方法…...

编程日记 2025/5/14 7:52:20

CTFSHOW-WEB入门-命令执行71-77

题目：web 71 题目：解题思路：分析可知highlight_file() 函数被禁了，先想办法看看根目录：cvar_export(scandir(dirname(‘/’))); 尝试一下发现很惊奇：（全是？）这种情况我也…...

编程日记 2025/5/14 8:13:05

[MRCTF2020]Ez_bypass1(md5绕过)

[MRCTF2020]Ez_bypass1(md5绕过) 这道题就是要绕过md5强类型比较，但是本身又不相等： md5无法处理数组，如果传入的是数组进行md5加密，会直接放回NULL，两个NuLL相比较会等于true； 所以?id[]1&gg…...

编程日记 2025/5/8 16:36:50

PPT演示设置：插入音频同步切换播放时长计算

PPT中插入音频&同步切换&放时长计算一、插入音频及音频设置二、设置页面切换和音频同步三、播放时长计算四、使用宏设置设置页面切换和音频同步一、插入音频及音频设置 1.插入音频：点击菜单栏插入-音频-选择PC上的音频（已存在的音频）或者录制音频（现场录制） …...

编程日记 2025/5/14 10:20:45

Modbus Slave RTU 在 AVP28335（兼容德州仪器TMS 320 28335）上实现含源码及注释。

今天先把题目先给出来， 在近两天会把源码 （含详细注释 ）及部署、测试结果给出来， 希望能给大家帮助。（原来这个程序在CSDN中，有小伙伴已经写了一些，但是发现里面埋了很多坑，例如&…...

编程日记 2025/5/12 0:43:46

以下是一份详细的 git-secret 使用教程，包含常见场景的 Bash 代码示例： 1. 安装 git-secret # Ubuntu/Debian sudo apt-get install git-secret# macOS (Homebrew) brew install git-secret# 其他 Linux (Snap) sudo snap install git-secret# 验证安装…...

编程日记 2025/5/11 4:20:10

防火墙安全策略

目录一.拓扑及需求二.需求分析三.配置详细信息防火墙： OA server： Web Server： PC1： 编辑PC2： PC3： 配置安全区域： 交换机： 四.需求实现以及测试： 1.…...

编程日记 2025/5/12 10:51:03

蓝桥杯python基础算法（2-2）——基础算法（D）——进制转换*

目录五、进制转换十进制转任意进制，任意进制转十进制例题 P1230 进制转换作业 P2095 进制转化作业 P2489 进制五、进制转换十进制转任意进制，任意进制转十进制 int_to_char "0123456789ABCDEF" def Ten_to_K(k, x):answer "…...

编程日记 2025/5/11 19:19:11

VSCode源码分析参考资料

VSCode Architecture Analysis - Electron Project Cross-Platform Best Practices 中文版 VSCode 架构分析 - Electron 项目跨平台最佳实践 Sihan Li博客上的vscode源码分析系列：分析了微服务架构、事件体系、资源管理、配置系统等文召博客上的vscode 源码解析…...

编程日记 2025/5/12 23:15:32

深入理解 Rust 模块中的路径与公开性：绝对路径、相对路径和 `pub` 的应用

1. 路径的两种形式：绝对路径与相对路径在 Rust 中，路径类似于文件系统中的目录路径，用来告诉编译器去哪里查找某个项。路径主要有两种形式： 绝对路径绝对路径从 crate 的根开始。对于当前 crate 的代码，绝对路径以关…...

编程日记 2025/5/12 20:54:07

DeepSeek R1 大模型本地部署指南

以下是部署DeepSeek R1大模型的详细Markdown指南，可直接保存为.md文件并分享： # DeepSeek R1 大模型本地部署指南**适用系统**：Windows 10/11 & Linux (Ubuntu 20.04)---## 目录 1. [硬件要求](#硬件要求) 2. [准备工作](#准备工作) 3. […...

编程日记 2025/5/13 5:04:19

从Proxmox VE开始：安装与配置指南

前言 Proxmox Virtual Environment (Proxmox VE) 是一个开源的虚拟化平台，基于Debian Linux，支持KVM虚拟机和LXC容器。它提供了一个强大的Web管理界面，方便用户管理虚拟机、存储、网络等资源。Proxmox VE广泛应用于企业级虚拟化、云计算和开…...

编程日记 2025/5/3 9:39:30

Docker 安装详细教程（适用于CentOS 7 系统）

目录步骤如下： 1. 卸载旧版 Docker 2. 配置 Docker 的 YUM 仓库 3. 安装 Docker 4. 启动 Docker 并验证安装 5. 配置 Docker 镜像加速总结前言 Docker 分为 CE 和 EE 两大版本。CE即社区版（免费，支持周期7个月）&#xf…...

编程日记 2025/5/13 4:09:57

前端 | 浅拷贝深拷贝

在前端开发中，我们经常需要复制对象或数组，但不同的复制方式可能会影响数据的完整性和应用的稳定性。本文将深入探讨浅拷贝（Shallow Copy）和深拷贝（Deep Copy）的区别、实现方式及适用场景。 1. 浅拷贝 1.…...

编程日记 2025/4/23 13:52:35

巧用 Cursor+Coze，轻松简化小程序开发

一、为啥要用 Cursor+Coze 简化小程序开发家人们，如今小程序简直火出圈啦！不管你是电商从业者，还是服务行业的工作者，又或是自媒体运营者，拥有一个小程序，就相当于给业务插上了腾飞的翅膀，能带来更多的流量和机会。但是，小程序开发的过程，那可真是充满了挑战。从最开…...

编程日记 2025/5/13 7:57:58

Spring Boot常用注解深度解析：从入门到精通

今天，这篇文章带你将深入理解Spring Boot中30常用注解，通过代码示例和关系图，帮助你彻底掌握Spring核心注解的使用场景和内在联系。一、启动类与核心注解 1.1 SpringBootApplication 组合注解： SpringBootApplication Confi…...

编程日记 2025/5/11 2:17:30

解决Mac安装软件的“已损坏，无法打开。您应该将它移到废纸篓”问题

mac安装软件时，如果出现这个问题，其实很简单首先打开终端，输入下面的命令 sudo xattr -r -d com.apple.quarantine 输入完成后，先不要回车，点击访达--应用程序--找到你无法打开的app图标，拖到终端窗口中…...

编程日记 2025/5/13 2:40:06

爱普生L3153打印机无线连接配置流程

家里使用的是移动宽带中兴路由器，有WPS功能，进入192.168.1.1管理员页面，用户名user，密码在路由器背面（可以登录后修改密码）。在网络-WLAN网络配置-WPS中，点击push button，激活路由器…...

编程日记 2025/5/13 3:15:57

第二十章存储函数

目录一、概述二、语法三、示例一、概述前面章节中，我们详细讲解了MySQL中的存储过程，掌握了存储过程之后，学习存储函数则肥仓简单，存储函数其实是一种特殊的存储过程，也就是有返回值的存储过程。存储函数的参数…...

编程日记 2025/5/14 4:41:13

pytorch实现门控循环单元 (GRU）

人工智能例子汇总：AI常见的算法和例子-CSDN博客特性GRULSTM计算效率更快，参数更少相对较慢，参数更多结构复杂度只有两个门（更新门和重置门）三个门（输入门、遗忘门、输出门）处理长时依赖一般适…...

编程日记 2025/5/14 8:18:14

unity报错不存在类型或者命名空间

导入资源或者打开项目时，突然发现多了一堆报错，如 Assets\2DGamekit\Utilities\DefaultPlayables\ScreenFader\ScreenFaderBehaviour.cs(5,19): error CS0234: The type or namespace name UI does not exist in the namespace UnityEngine (are you mi…...

编程日记 2025/5/12 11:50:06

Qt展厅播放器/多媒体播放器/中控播放器/帧同步播放器/硬解播放器/监控播放器

一、前言说明音视频开发除了应用在安防监控、视频网站、各种流媒体app开发之外，还有一个小众的市场，那就是多媒体展厅场景，这个场景目前处于垄断地位的软件是HirenderS3，做的非常早而且非常全面，都是通用的需求&…...

编程日记 2025/5/14 2:57:27

Spring Bean 的生命周期介绍

Spring Bean 的生命周期涉及多个阶段，从实例化到销毁，在开发中我们可以通过各种接口和注解介入这些阶段来定制化自己的功能。以下是详细的生命周期流程： 1. Bean 的实例化（Instantiation） 方式：通过构造函…...

编程日记 2025/5/14 4:35:29

奥卡姆剃刀原理：用简单的力量，解锁复杂的世界

奥卡姆剃刀原理大名鼎鼎的奥卡姆剃刀原理（Occam’s Razor），其含义很简单，就一句话：“如无必要，勿增实体”。这句看似简单却蕴含着深刻智慧的话，是由14世纪的英格兰逻辑学家、圣方济各会修士…...

编程日记 2025/5/12 13:39:44

STM32 串口发送与接收

接线图代码配置根据上一章发送的代码配置，在GPIO配置的基础上需要再配置PA10引脚做RX接收，引脚模式可以选择浮空输入或者上拉输入，在USART配置串口模式里加上RX模式。配置中断 //配置中断 USART_ITConfig(USART1, USART_IT_RXNE, ENABLE…...

编程日记 2025/5/14 1:26:16

如何生成强密码：提高网络安全性的全面指南

引言在数字化时代，密码的安全性至关重要。随着我们在社交媒体、电子邮件、在线银行等平台上储存越来越多的个人信息，强密码的使用变得更加关键。强密码能有效防止暴力破解、字典攻击等安全威胁。因此，在本文中，我们将深入探讨如…...

编程日记 2025/5/13 22:35:09

如何不更新application.yml而更新spring的配置

更改应用程序外部属性的位置默认情况下，来自不同来源的属性会按定义的顺序添加到 Spring 中（有关确切顺序，请参阅“Spring Boot 功能”部分中的“外部化配置”）。Environment 您还可以提供以下系统属性（或环境变量&…...

编程日记 2025/5/12 15:15:31

【Unity踩坑】Unity项目管理员权限问题（Unity is running as administrator ）

问题描述： 使用Unity Hub打开或新建项目时会有下面的提示。解决方法： 打开“本地安全策略”： 在Windows搜索栏中输入secpol.msc并回车，或者从“运行”对话框（Win R，然后输入secpol.msc）启…...

编程日记 2025/5/12 12:47:16

【JavaScript】《JavaScript高级程序设计 (第4版) 》笔记-Chapter1-什么是 JavaScript

一、什么是 JavaScript 虽然 JavaScript 和 ECMAScript（发音为“ek-ma-script”） 基本上是同义词，但 JavaScript 远远不限于 ECMA-262 所定义的那样。没错，完整的 JavaScript 实现包含以下几个部分。核心（ECMAScript&…...

编程日记 2025/5/12 16:00:17

队列 + 宽搜（4题）

目录 1.n叉树的层序遍历 2.二叉树的锯齿形层序遍历 3.二叉树的最大宽度 4.在每个树行中找最大值 1.n叉树的层序遍历 429. N 叉树的层序遍历 - 力扣（LeetCode） 我们只需要把某个节点出队的时候把它的孩子节点添加进来即可。出队的次数就是最开始队列…...

编程日记 2025/5/13 11:42:47

二、面向对象

一、结构体类型结构体类型是一种自定义类型，用于创建我们游戏或者实际业务中的自定义类型. 代码中变量有通用的，可以使用结构体，包裹起来。 1、成员变量 /// <summary> /// 英雄结构体 /// </summary> struct Hero {//成员p…...

编程日记 2025/5/9 9:55:50

【DeepSeek背后的技术】系列二：大模型知识蒸馏（Knowledge Distillation）

目录 1 引言2 操作步骤和公式说明2.1 准备教师模型（Teacher Model）和学生模型（Student Model）2.2 生成软标签（Soft Labels）2.3 定义蒸馏损失函数2.4 训练学生模型2.5 调整超参数2.6 评估与部署 3 其他知识蒸…...

编程日记 2025/5/13 4:09:49

PyQt4学习笔记2】QMainWindow

目录一、创建 QMainWindow 组件 1. 创建工具栏 2. 创建停靠窗口 3. 设置状态栏 4. 设置中央窗口部件二、QMainWindow 的主要方法 1. addToolBar() 2. addDockWidget() 3. setStatusBar() 4. setCentralWidget() 5. menuBar() 6. saveState() 和 restoreState() 三、QMainWind…...

编程日记 2025/5/12 11:19:59

《海丰县蔡氏简介》前言

《海丰县蔡氏简介》前言蔡惠进主编汕尾市海陆丰蔡姓祖先基本是福建人， 在宋朝时迁至海丰， 因受潮汕文化、客家文化、广府文化、政治归属等系列因素影响， 形成了闽南人一种新的文化， 既有传统的闽南文化， 又有潮汕…...

编程日记 2025/5/13 13:38:50

背包DP

一、背包DP问题分类

二、0-1背包问题

问题描述

状态定义

状态转移方程

C++实现

关键点

三、完全背包问题

问题描述

状态转移方程

C++实现

应用场景

四、多重背包问题

问题描述

优化方法

C++实现

五、分组背包问题

问题描述

状态转移方程

C++实现

六、常见问题与调试技巧

1. 初始化陷阱

2. 遍历顺序总结

3. 测试用例设计

七、典型例题与代码

1. 分割等和子集（LeetCode 416）

2. 零钱兑换 II（LeetCode 518）

八、性能优化进阶

相关文章：