---
title: "分组背包问题"
created: 2025-11-28
tags:
  - 算法
---

# 分组背包问题

## 题目  [分组背包问题](https://www.acwing.com/problem/content/9/)

![[image-6e35e2c5.png]]

## 思路分析

![[image-1d734ad4.png]]

从另一个角度 多加一个维度

现在是每类物品里选一个 多了个类这一维

但是因为只能选一个 所以还是可以当做01去写

朴素做法

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

using namespace std;

const int N = 110;

//由n种物品变成了n类物品 然后又要在每类里面去选

//所以就是多了一维

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

int f[N][N];

int n, m;

int main()

{

    cin>>n>>m;

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

        cin>>s[i];

        for(int j=0;j<s[i];j++){

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

        }

    }

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

        for(int j=0;j<=m;j++){

            f[i][j]=f[i-1][j];  //不选

            for(int k=0;k<s[i];k++){

                //第i类物品里的第k种

                if(j>=v[i][k])

                    f[i][j]=max(f[i][j],f[i-1][j-v[i][k]]+w[i][k]);

            }

        }

    }

    cout<<f[n][m];

    return 0;

}
```

因为只用到了第i-1列，所以可以仿照01背包的套路逆向枚举体积

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

using namespace std;

const int N = 110;

//由n种物品变成了n类物品 然后又要在每类里面去选

//所以就是多了一维

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

int f[N];

int n, m;

int main()

{

    cin>>n>>m;

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

        cin>>s[i];

        for(int j=0;j<s[i];j++){

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

        }

    }

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

        //用的上一层的数据 从大到小遍历

        for(int j=m;j>=0;j--){

            for(int k=0;k<s[i];k++){

                if(j>=v[i][k])

                    f[j]=max(f[j],f[j-v[i][k]]+w[i][k]);

            }

        }

    }

    cout<<f[m];

    return 0;

}
```

发现万变不离其宗

再往后可能就是物品分类 且其中可选多个（又分带不带物品数量限制）

## 代码实现

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

using namespace std;

const int N = 110;

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

int f[N][N];

int n, m;

int main()

{

    cin>>n>>m;

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

        cin>>s[i];

        for(int j=0;j<s[i];j++){

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

        }

    }

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

        for(int j=0;j<=m;j++){

            f[i][j]=f[i-1][j];

            for(int k=0;k<s[i];k++){

                if(j>=v[i][k])

                    f[i][j]=max(f[i][j],f[i-1][j-v[i][k]]+w[i][k]);

            }

        }

    }

    cout<<f[n][m];

    return 0;

}
```

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

using namespace std;

const int N = 110;

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

int f[N];

int n, m;

int main()

{

    cin>>n>>m;

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

        cin>>s[i];

        for(int j=0;j<s[i];j++){

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

        }

    }

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

        for(int j=m;j>=0;j--)

            for(int k=0;k<s[i];k++)

                if(j>=v[i][k])

                    f[j]=max(f[j],f[j-v[i][k]]+w[i][k]);

    cout<<f[m];

    return 0;

}
```

## 同类题型

## 视频讲解

---
⬅️ [[二维费用的背包问题|二维费用的背包问题]] 🏠 [[00-刷题理模型]] ➡️ [[min属性 潜水员|min属性 潜水员]]