商城网站建设费用,免费可商用的素材网站,免费 网站 cms,网站开发整套资料目录
二维费用背包问题
问题描述#xff1a;
解决方法#xff1a;
方法一#xff1a;
代码实现#xff1a;
方法二#xff1a;
代码实现#xff1a; 背包问题第五讲——二维费用背包问题 背包问题是一类经典的组合优化问题#xff0c;通常涉及在限定容量的背包中…目录
二维费用背包问题
问题描述
解决方法
方法一
代码实现
方法二
代码实现 背包问题第五讲——二维费用背包问题 背包问题是一类经典的组合优化问题通常涉及在限定容量的背包中选择物品以最大化某种价值或利益。问题的一般描述是有一个背包其容量为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表示当前背包的重量不超过jk表示当前背包的第二种资源不超过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背包的写法进行改进。 代码实现
#includeiostream
using namespace std;
int N,V,M;
int v[1005],m[1005],w[1005],dp[1005][1005];
//dp[i][j]表示体积为i重量为j的情况下所获得最大价值
int main(){cinNVM;//N个物品V背包体积M背包所承受最大重量for(int i1;iN;i){cinv[i]m[i]w[i];for(int jV;jv[i];j--){for(int kM;km[i];k--){//这里按照01背包一维优化分两个for来写dp[j][k]max(dp[j][k],dp[j-v[i]][k-m[i]]w[i]);//要么选第i个物品要么就不选}}}coutdp[V][M]endl;return 0;
} 上一篇文章背包九讲——混合背包问题-CSDN博客
背包问题是经典之经典每一位算法入门学者必学的内容里面的优化涉及到的也非常具有思维性值得大家好好学习。由于笔者水平有限一些方面可能也存在着问题望大家理解支持有错误就指出改正大家一起进步执笔至此感触彼多全文将至落笔为终感谢各位的支持下篇更新分组背包问题。
