《背包问题：C++ 中的“资源分配”与“空间压缩”》-北京尧图网络

你是一个货车司机CPU车斗容量有限背包容量。货场里有一堆货物物品每个货物有重量和价值。你的目标是在不超重的前提下装下价值最高的货物组合。模块一0-1 背包标准二维版1. 思路讲解定义dp[i][w]考虑前i件物品背包容量为w时能装的最大价值。对于第i件物品面临两个选择不装dp[i][w] dp[i-1][w]价值继承上一轮。装dp[i][w] dp[i-1][w-weight[i]] value[i]腾出空间加上价值。取两者最大值。2. 代码详解cppcpp#include vector #include algorithm using namespace std; class Solution { public: int knapsack(int N, int W, vectorint wt, vectorint val) { // dp[i][w]: 前i个物品容量w下的最大价值 vectorvectorint dp(N 1, vectorint(W 1, 0)); for (int i 1; i N; i) { // 遍历物品 for (int w 1; w W; w) { // 遍历容量 // 如果当前物品重量超过当前背包容量没法装 if (wt[i - 1] w) { dp[i][w] dp[i - 1][w]; } else { // 核心装 vs 不装 dp[i][w] max( dp[i - 1][w], // 不装 dp[i - 1][w - wt[i - 1]] val[i - 1] // 装 ); } } } return dp[N][W]; } };C 细节wt[i-1]是因为数组下标从 0 开始而 DP 下标从 1 开始为了省去初始化第 0 行的麻烦。模块二0-1 背包一维优化版 - 滚动数组1. 思路讲解观察二维 DP 表发现dp[i][...]只依赖于dp[i-1][...]。我们可以将二维压缩为一维dp[w]。关键难点为什么容量w必须倒序遍历如果正序遍历dp[w-weight[i]]可能已经被本轮第 i 个物品更新过了这就变成了“完全背包”物品可重复选取。倒序遍历能保证dp[w-weight[i]]一定是上一轮i-1的数据。2. 代码详解cppcppclass Solution { public: int knapsack(int N, int W, vectorint wt, vectorint val) { vectorint dp(W 1, 0); // 一维数组 for (int i 0; i N; i) { // 遍历物品 // 关键倒序遍历容量防止数据污染 for (int w W; w wt[i]; w--) { // dp[w] 相当于二维的 dp[i-1][w] // dp[w-wt[i]] 相当于二维的 dp[i-1][w-wt[i]] dp[w] max(dp[w], dp[w - wt[i]] val[i]); } } return dp[W]; } };口诀“0-1 背包倒着走完全背包顺着走”。模块三分割等和子集背包思想的应用1. 思路讲解能不能将一个数组分成两个和相等的子数组转化为能不能从数组中挑选一些数使得它们的和恰好等于sum/2。这是一个“背包容量为 sum/2物品重量为 nums[i]价值也为 nums[i]” 的 0-1 背包问题。2. 代码详解cppcppclass Solution { public: bool canPartition(vectorint nums) { int sum 0; for (int num : nums) sum num; if (sum % 2 ! 0) return false; // 奇数不可能平分 int target sum / 2; vectorbool dp(target 1, false); dp[0] true; // 什么都不选和为0永远成立 for (int num : nums) { // 遍历物品 // 遍历容量倒序0-1背包特性 for (int j target; j num; j--) { // 如果减去当前num剩下的重量能被凑出来那当前重量也能被凑出来 dp[j] dp[j] || dp[j - num]; } } return dp[target]; } };思路dp[j]是布尔类型表示能否凑出和为j。这里使用了逻辑或||。谢谢

《背包问题：C++ 中的“资源分配”与“空间压缩”》

相关推荐

杭州系统门窗口碑好的品牌推荐

负指数信号梯形成型 Python 实现：3 参数调优与 FPGA 递推公式推导

Codex 实战：用项目结果反推能力

更多资讯

Flutter与鸿蒙融合中的依赖版本管理实践

LightRAG架构优化：提升AI问答系统性能的关键技术

OpenCV与C#实现工业级直线卡尺测量工具

YOLO v11架构升级：从检测框架到端到端感知引擎

Python生成器原理与应用：从惰性求值到协程实践

NI工业AI测试：边缘原生与信号级嵌入的闭环实践

今日更新

基于MATLAB的CRI显色指数计算：从SPD光谱到Ra的完整流程

JSP+Servlet+MySQL博客系统源码部署与优化全攻略

蜂窝调度算法 MATLAB 实现：比例公平、轮询与最大 C/I 对比

本周精选

AI驱动的自动化专利分析平台技术解析

LeetCode-Go 题解：1252. Cells with Odd Values in a Matrix（奇数值单元格计数）双解法剖析

在线答疑系统Java毕设实战：Spring Boot前后端分离与状态流转

本月热门

基于YOLO的焊缝缺陷检测：从数据标注到工业部署全流程实践

分布式服务的决策记录

创业产品的首版范围

读完文章，想聊聊您的网站？