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

【背包问题】二维费用的背包问题

目录

二维费用的背包问题详解

总结:

空间优化:

1. 状态定义

2. 状态转移方程

3. 初始化

4. 遍历顺序

5. 时间复杂度

例题

1,一和零

2,盈利计划


二维费用的背包问题详解

前面讲到的01背包中,对物品的限定条件只有一个体积,而在二维费用的背包问题中,相当于增加了一个限定条件,比如:

【问题描述】

  • 输入

    • 物品数量 N,每个物品有重量 wi​、体积 vi​ 和价值 vali​。

    • 背包最大承重 W,最大体积 V。

    • 目标:选择物品装入背包,使得总重量 ≤ W,总体积 ≤ V,且总价值最大。

加了一个限定条件重量,那么状态表示也需加上一维。二维费用的背包问题时01背包问题的一个延申,状态表示和状态转移方程的分析与01背包类似。

状态表示是dp[i][j][k],表示前i个物品,在重量限制j和体积限制k下的最大价值

状态转移方程就是:dp[i][j][k] = max([i-1]dp[j][k], dp[i][j - w[i]][k - v[i]] + val[i]),推理过程与01背包类似。

总结:

常规的0-1背包问题可以用动态规划来解决,状态通常是dp[i][j]表示前i个物品,在容量j下的最大价值。对于二维费用的情况,可能需要扩展状态到两个维度。比如,状态可能是dp[i][j][k],表示前i个物品,在重量限制j和体积限制k下的最大价值。但这样的话,状态空间会变得很大,尤其是当j和k都较大的时候,时间和空间复杂度可能很高。不过,可能可以通过优化来减少空间的使用,比如使用滚动数组

空间优化:

在常规的0-1背包问题中,我们可以将二维的dp优化为一维数组,通过逆序遍历容量来避免覆盖之前的状态。那么在二维费用的情况下,使用二维的dp数组,而不是三维的。例如,状态dp[j][k]表示在重量j和体积k的限制下能获得的最大价值。这样的话,每次处理一个物品时,需要从后往前更新这两个维度,以避免重复选择同一物品。这可能需要双重循环,遍历重量和体积的容量。

1. 状态定义
  • 定义二维数组 dp[j][k],表示背包在承重 j 和体积 k 的限制下能获得的最大价值。

  • 最终目标:求解 dp[W][V]。

2. 状态转移方程

对每个物品i,逆序更新所有可能的重量和体积组合:

dp[j][k]=max⁡(dp[j][k], dp[j−wi][k−vi]+vali)

条件:j≥wi 且 k≥vi

3. 初始化
  • dp[0][0]=0(空背包价值为0)。

  • 其他位置初始化为0,表示未装入任何物品时的初始状态。

4. 遍历顺序
  • 外层循环:遍历每个物品 i。

  • 内层双循环

    • 重量 j 从 W 逆序递减至 wi​。

    • 体积 k 从 V 逆序递减至 vi​。
      确保每个物品仅被选择一次。

    • 5. 时间复杂度
    • O(N×W×V),适用于 W 和 VV均较小的情况(如 W,V≤10^3)。

例题

1,一和零

本题链接:474. 一和零 - 力扣(LeetCode)

思路:

从strs数组中选取子集,有两个限定条件m和n。相当于从背包中选取元素,有两个限定条件。

 

class Solution {
public:int findMaxForm(vector<string>& strs, int m, int n) {int len=strs.size();vector<vector<vector<int>>> dp(len+1,vector<vector<int>>(m+1,vector<int>(n+1)));for(int i=1;i<=len;i++){int a=0,b=0;for(auto& ch:strs[i-1])if(ch=='0') a++;else b++;for(int j=0;j<=m;j++)for(int k=0;k<=n;k++){dp[i][j][k]=dp[i-1][j][k];if(j>=a&&k>=b)dp[i][j][k]=max(dp[i][j][k],dp[i-1][j-a][k-b]+1);}}return dp[len][m][n];}
};

 空间优化后的代码
 

class Solution {
public:int findMaxForm(vector<string>& strs, int m, int n) {int len=strs.size();vector<vector<int>> dp(m+1,vector<int>(n+1));for(int i=1;i<=len;i++){int a=0,b=0;for(auto& ch:strs[i-1])if(ch=='0') a++;else b++;for(int j=m;j>=a;j--)for(int k=n;k>=b;k--)dp[j][k]=max(dp[j][k],dp[j-a][k-b]+1);}return dp[m][n];}
};

2,盈利计划

本题链接:879. 盈利计划 - 力扣(LeetCode)

思路:

 

 

class Solution {
public:int profitableSchemes(int n, int m, vector<int>& g, vector<int>& p) {int len=g.size();const int MOD=1e9+7;vector<vector<vector<int>>> dp(len+1,vector<vector<int>>(n+1,vector<int>(m+1)));for(int j=0;j<=n;j++)dp[0][j][0]=1;for(int i=1;i<=len;i++)for(int  j=0;j<=n;j++)for(int k=0;k<=m;k++){dp[i][j][k]=dp[i-1][j][k];if(j>=g[i-1])dp[i][j][k]+=dp[i-1][j-g[i-1]][max(0,k-p[i-1])];dp[i][j][k]%=MOD;}return dp[len][n][m];}
};

 空间优化后的代码

class Solution {
public:int profitableSchemes(int n, int m, vector<int>& g, vector<int>& p) {int len=g.size();const int MOD=1e9+7;vector<vector<int>> dp(n+1,vector<int>(m+1));for(int j=0;j<=n;j++)dp[j][0]=1;for(int i=1;i<=len;i++)for(int j=n;j>=g[i-1];j--)for(int k=m;k>=0;k--){dp[j][k]+=dp[j-g[i-1]][max(0,k-p[i-1])];dp[j][k]%=MOD;}return dp[n][m];}
};

http://www.lryc.cn/news/531033.html

相关文章:

  • Golang 并发机制-5:详解syn包同步原语
  • 实验六 项目二 简易信号发生器的设计与实现 (HEU)
  • 如何用微信小程序写春联
  • LabVIEW无人机航线控制系统
  • C++哈希表深度解析:从原理到实现,全面掌握高效键值对存储
  • Vue.js组件开发-实现字母向上浮动
  • 自研有限元软件与ANSYS精度对比-Bar2D2Node二维杆单元模型-四连杆实例
  • 04树 + 堆 + 优先队列 + 图(D1_树(D11_伸展树))
  • c语言练习题【数据类型、递归、双向链表快速排序】
  • SliverAppBar的功能和用法
  • 五、定时器实现呼吸灯
  • Elasticsearch的索引生命周期管理
  • 【大模型理论篇】最近大火的DeepSeek-R1初探系列1
  • 【数据结构】(4) 线性表 List
  • 【C++ STL】vector容器详解:从入门到精通
  • OpenAI推出Deep Research带给我们怎样的启示
  • 洛谷[USACO08DEC] Patting Heads S
  • CSS 溢出内容处理:从基础到实战
  • Spring Boot项目如何使用MyBatis实现分页查询
  • 飞行汽车中的无刷外转子电机、人形机器人中的无框力矩电机技术解析与应用
  • FreeRTOS学习 --- 队列集
  • 【R语言】R语言安装包的相关操作
  • 15.[前端开发]Day15-HTML+CSS阶段练习(网易云音乐四)
  • 【基于SprintBoot+Mybatis+Mysql】电脑商城项目之用户登录
  • 测试方案和测试计划相同点和不同点
  • c++提取矩形区域图像的梯度并拟合直线
  • Unity Shader Graph 2D - 角色身体电流覆盖效果
  • 【LLM-agent】(task4)搜索引擎Agent
  • 携程Java开发面试题及参考答案 (200道-下)
  • GWO优化SVM回归预测matlab