分组背包c

分组背包问题是背包问题的一种扩展，与 01 背包、完全背包问题不同之处在于，每个物品都有一个所属的组别，同一组内的物品最多只能选一个。其基本思路是将物品按组别划分，对于每一组物品，只能选择其中的一个物品放入背包中。以下是分组背包问题的C++代码实现。

#include <iostream>
#include <cstring>
using namespace std;

const int N = 110, M = 1010;
int f[M], w[N][N], v[N][N], s[N];

int main()
{
    int n, m;
    cin >> n >> m;

    for (int i = 1; i <= n; i ++ )
    {
        cin >> s[i];
        for (int j = 0; j < s[i]; j ++ ) cin >> w[i][j] >> v[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 >= w[i][k])
                    f[j] = max(f[j], f[j - w[i][k]] + v[i][k]);

    cout << f[m] << endl;

    return 0;
}

其中，$f[j]$ 表示背包容量为 $j$ 时能够获取的最大价值。对于第 $i$ 组物品，$s[i]$ 表示该组物品的数量，$w[i][j]$ 和 $v[i][j]$ 分别表示该组中第 $j$ 个物品的重量和价值。利用三重循环，我们可以求解出分组背包问题的最优解。