DP(分组背包问题)

分组背包问题就是在01背包上加上了分组的条件就是，取得是每一组的最大值。

f[N][N]就是前i组物品中选，当前体积小于等于j的最大值，v[][]体积，w[][]价值，s[]代表第i组的物品个数。

如果不选就是f[i][j] = f[i-1][j]，如果选的话就是f[i][j] = max(f[i][j],f[i-1][j-v[i][k]]+w[i][k])；这就是状态转移方程。

如果是一维的就是根据0-1背包一样逆序操作，f[j] = max(f[j],f[j-v[i][k]]+w[i][k])

P1757 通天之分组背包

P1757 通天之分组背包 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

代码

//二维
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
constexpr int N = 1050;
int w[N][N],p[N][N],s[N];
int f[N][N];
void solve(){
	int weight,n;
	cin>>weight>>n;

	for(int i = 1;i<=n;i++){
		int tmpw,tmpp,k;
		cin>>tmpw>>tmpp>>k;
		s[k]++;
		w[k][s[k]] = tmpw;
		p[k][s[k]] = tmpp;
	}
	for(int i = 1;i<=n;i++){
		for(int j = 0;j<=weight;j++){
			f[i][j] = f[i-1][j];
			for(int m = 0;m<=s[i];m++){
				if(j>=w[i][m]){
					f[i][j] = max(f[i][j],f[i-1][j-w[i][m]]+p[i][m]);
				}
			}
		}
	}
	cout<<f[n][weight];
}
int main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	solve();
}

//一维
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
constexpr int N = 1050;
int w[N][N],p[N][N],s[N];
int f[N];
void solve(){
	int weight,n;
	cin>>weight>>n;

	for(int i = 1;i<=n;i++){
		int tmpw,tmpp,k;
		cin>>tmpw>>tmpp>>k;
		s[k]++;
		w[k][s[k]] = tmpw;
		p[k][s[k]] = tmpp;
	}
	for(int i = 1;i<=n;i++){
		for(int j = weight;j>0;j--){
			f[j] = f[j];
			for(int m = 0;m<=s[i];m++){
				if(j>=w[i][m]){
					f[j] = max(f[j],f[j-w[i][m]]+p[i][m]);
				}
			}
		}
	}
	cout<<f[weight];
}
int main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	solve();
}