分组背包问题笔记

分组背包是选不同的组，每个组中只能选一个物品。分组背包就是01背包的变种，多重背包就是特殊的分组背包。

//分组背包
#include<iostream>
using namespace std;
const int N = 110;
int f[N], v[N], w[N], n, m;

int main()
{
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	cin >> n >> m;
	for (int i = 0; i < n; ++i)
	{
		int s; cin >> s;
		//初始化每组的数据
		for (int j = 0; j < s; ++j) cin >> v[j] >> w[j];
		for (int j = m; j >= 0; --j)
		{
			for (int k = 0; k < s; ++k)
			{
				//这里必须加上判断，因为这里j没有做限制
				if (j - v[k] >= 0) f[j] = max(f[j], f[j - v[k]] + w[k]);
			}
		}
	}

	cout << f[m];
	return 0;
}

?还有一种方法优化空间：就是将物品放在外层循环：

#include <bits/stdc++.h>

using namespace std;

const int M = 110;
int dp[M], last[M];
int N, V, S, v, w;

int main()
{
    cin >> N >> V;
    for (int i = 0; i < N; i++)
    {
        cin >> S;
        for (int j = 0; j < S; j++)
        {
            cin >> v >> w;
            for (int k = V; k >= v; k--)
                dp[k] = max(dp[k], last[k - v] + w);
        }
        memcpy(last, dp, sizeof dp);
    }
    cout << dp[V] << endl;

    return 0;
}

每次last数组保存上一次的状态，每个物品都会更新一次f[0]到f[V],如果不记录上一次的状态，不需要加上if条件(循环k中已经加了限制了)，就必须写成二维的数组了。这时就需要加上if条件了。优化掉的空间就是开数组的空间。

for(int i=1;i<=n;i++){
        int s;
        scanf("%d",&s);
        for(int k=1;k<=s;k++){//第i组第k个物品
            int a,b;
            scanf("%d%d",&a,&b);
            for(int j=v;j>=0;j--){
                f[i][j]=max(f[i][j],f[i-1][j]);
                if(j>=a) f[i][j]=max(f[i][j],f[i-1][j-a]+b);
            }
        }
    }

一维数组无法取得上一层的状态 。

?

?