---
title: "二维费用的背包问题"
created: 2025-11-28
tags:
  - 算法
---

# 二维费用的背包问题

## 题目 [二维费用的背包问题](https://www.acwing.com/problem/content/8/)

![[image-70d7c9ed.png]]

## 思路分析

如果在前面问题的基础上 加上一个限制呢

比如 背包不仅有容积（体积）的限制 还会有重量的限制

加上这么一个维度 代码应该如何变

其实就是和枚举体积一样 再加一个循环 枚举重量即可

![[image-54c0d772.png]]

## 代码实现

朴素

```cpp
#include<bits/stdc++.h>

using namespace std;

const int N=1010,M=110;

int v[N],m[N],w[N];//每件物品的体积、重量和价值

int f[N][M][M];

int n,m1,m2;// 物品数量、背包容积上限、背包重量上限

int main()

{

    cin>>n>>m1>>m2;

    for(int i=1;i<=n;i++)

        cin>>v[i]>>m[i]>>w[i];

    for(int i=1;i<=n;i++)

    {

        for(int j1=0;j1<=m1;j1++){

            for(int j2=0;j2<=m2;j2++){//加一层循环即可 状态转移时也要多一

                f[i][j1][j2]=f[i-1][j1][j2];

                if(j1>=v[i] && j2>=m[i])

                     f[i][j1][j2]=max(f[i-1][j1][j2],f[i-1][j1-v[i]][j2-m[i]]+w[i]);

            }

        }

    }

    cout<<f[n][m1][m2];

    return 0;

}
```

滚动优化

```cpp
#include<bits/stdc++.h>

using namespace std;

const int N=1010,M=110;

int v[N],m[N],w[N];

int f[M][M];

int n,m1,m2;

int main()

{

    cin>>n>>m1>>m2;

    for(int i=1;i<=n;i++)

        cin>>v[i]>>m[i]>>w[i];

    for(int i=1;i<=n;i++)

    {

        for(int j1=m1;j1>=v[i];j1--){

            for(int j2=m2;j2>=m[i];j2--){

                f[j1][j2]=max(f[j1][j2],f[j1-v[i]][j2-m[i]]+w[i]);

            }

        }

    }

    cout<<f[m1][m2];

    return 0;

}
```

## 同类题型

## 视频讲解

---
⬅️ [[01背包问题|01背包问题]] 🏠 [[00-刷题理模型]] ➡️ [[分组背包问题|分组背包问题]]