再谈二维费用背包

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

二维费用背包问题是经典的动态规划问题之一，与普通的背包问题不同，它引入了两种不同的费用。问题的描述通常是这样的：给定一组物品，每个物品有两种费用（比如重量和体积），以及每个物品对应的价值。目标是选择一些物品放入背包中，使得在两种费用的限制下，背包中物品的总价值最大。 问题的状态转移方程通常表示为： dp[j][k]=max(dp[j][k],dp[j-v[i]][k-m[i]]+w[i]); 其中：dp[j][k]表示在考虑体积为j重量为k的情况下的最大总价值。 请注意，以上是一般形式的二维费用背包问题。具体问题的实现可能会有一些差异，具体问题的要求需要根据实际情况进行调整。

这里用acwing上的例题：8. 二维费用的背包问题 - AcWing题库

#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;
}

其实二维费用背包没有什么特别说的，就是01背包的推广，所谓道生一，一生二，二生三，三生万物。既然有二维费用背包，那是不是就有三维、四维……

具体的解法都是雷同的，这里不再解释，这里二维费用背包谈的比较浅，一些地方写的不是很好，有错误的地方请大家指出，共同进步，感谢大家支持。下篇更新分组背包。