背包九讲——二维费用背包问题

目录

二维费用背包问题 

问题描述：

解决方法：

方法一：

代码实现：

方法二：

代码实现：

背包问题第五讲——二维费用背包问题

背包问题是一类经典的组合优化问题，通常涉及在限定容量的背包中选择物品，以最大化某种价值或利益。问题的一般描述是：有一个背包，其容量为C；有一组物品，每个物品有重量w和价值v。目标是选择一些物品放入背包，使得它们的总重量不超过背包容量，同时总价值最大。
二维费用背包问题则是背包问题的变体，在背包问题中它只限定物品的重量，二维费用背包会再限定一个维度（体积），在既满足背包容量和既满足背包体积的情况下，使价值最大化。

二维费用背包问题 

二维费用背包问题是一种组合优化问题，它是经典的背包问题的扩展。在这个问题中，每件物品具有两个不同的属性，通常被称为“费用”或“资源限制”，以及一个价值。问题的目标是在给定的两种资源限制下，选择一组物品，使得它们的总价值最大。

二维费用背包呢，博主觉得是二重01背包的进化体，之前我们讨论的都是只有一个限定背包容量，比如在背包容量为V所能获得的价值，现在二维费用背包就是又加上了重量（第二维），比如背包容量为V且背包重量不能超过为M所能获得的价值。

---

问题描述：

- 有一组物品，每件物品都有一个重量（或体积）w[i]和价值v[i]。
- 有两种资源的限制，分别用W和U表示，对应于背包的承重和空间限制。
- 每件物品除了有一个重量w[i]，还有一个额外的属性u[i]，表示它占用的第二种资源的量。
- 背包可以选择装入或者不装入每件物品，但每件物品只能选择一次。
- 问题的目标是确定应该选择哪些物品，以便在不超过背包的重量W和第二种资源限制U的情况下，使得背包中物品的总价值最大。

题目可以参考一下这个：8. 二维费用的背包问题 - AcWing题库

题目描述基本跟01背包没有什么区别，无非就是多了一个限定条件，我们要在满足此两个条件的基础上去求最大价值。01背包问题之前dp只是定义了一个维度解决一个限定条件的问题，那么我们可以再去扩展一维，那么就可以解决两个限定条件了，我们会发现，这样的动态规划们还可以优化一个维度，这两个方法分别对应下面两个方法。 

---

解决方法：

方法一：

数学上，我们可以使用动态规划来解决这个问题。由于我们是二维的背包，那么定义一个三维数组dp[i][j][k]，其中i表示考虑到第i件物品，j表示当前背包的重量不超过j，k表示当前背包的第二种资源不超过k。dp[i][j][k]的值表示在这些条件下的最大价值。

状态转移方程如下：
dp[i][j][k] = max(dp[i-1][j][k], dp[i-1][j-w[i]][k-u[i]] + v[i]) if j >= w[i] && k >= u[i]

其中，dp[i-1][j][k]表示不选择第i件物品时的最大价值，而dp[i-1][j-w[i]][k-u[i]] + v[i]表示选择第i件物品时的最大价值。

最终，问题的解是dp[N][W][U]，其中N是物品的总数。

代码实现：

// 遍历所有物品for (int i = 1; i <= n; i++) {for (int j = 0; j <= W; j++) {for (int k = 0; k <= U; k++) {if (j >= weights[i - 1] && k >= volumes[i - 1]) {// 状态转移方程：选或不选第i件物品dp[i][j][k] = max(dp[i - 1][j][k], dp[i - 1][j - weights[i - 1]][k - volumes[i - 1]] + values[i - 1]);} else {// 如果背包无法容纳当前物品，则不选择该物品dp[i][j][k] = dp[i - 1][j][k];}}}}// 返回背包能够容纳的最大价值return dp[n][W][U];

---

方法二：

根据上面的代码，我们可以看出来第一个for循环是有生存周期的，第i个状态只与第i-1个状态有关，所有的第i个状态都是从第i-1个状态转移过来的，与前i-2个状态无关，那么我们可以利用这一点，去滚动数组，此时第i个状态更新便可以从前面的状态转移过来，从而覆盖掉上一个状态的答案，以此类推。这样我们便可以优化掉第一维度，减少了空间复杂度。其实二维费用背包没有什么特别说的，就是01背包的推广，所谓道生一，一生二，二生三，三生万物。既然有二维费用背包，那是不是就有三维、四维……，那么我们可以根据01背包的写法进行改进。

代码实现：

#include<iostream>
using namespace std;
int N,V,M;
int v[1005],m[1005],w[1005],dp[1005][1005];
//dp[i][j]表示体积为i重量为j的情况下所获得最大价值
int main(){cin>>N>>V>>M;//N个物品V背包体积M背包所承受最大重量for(int i=1;i<=N;i++){cin>>v[i]>>m[i]>>w[i];for(int j=V;j>=v[i];j--){for(int k=M;k>=m[i];k--){//这里按照01背包一维优化分两个for来写dp[j][k]=max(dp[j][k],dp[j-v[i]][k-m[i]]+w[i]);//要么选第i个物品要么就不选}}}cout<<dp[V][M]<<endl;return 0;
}

---

上一篇文章：背包九讲——混合背包问题-CSDN博客 

背包问题是经典之经典，每一位算法入门学者必学的内容，里面的优化涉及到的也非常具有思维性，值得大家好好学习。由于笔者水平有限，一些方面可能也存在着问题，望大家理解支持，有错误就指出改正，大家一起进步，执笔至此，感触彼多，全文将至，落笔为终，感谢各位的支持，下篇更新分组背包问题。