AcWing 9 分組背包問題 題解 （動态規劃—DP—背包問題）

思路： 考慮每種物品拿一個與考慮01背包問題類似

#include<iostream>

using namespace std;

const int N = 110;

int n, m;
int v[N][N], w[N][N];
int f[N];
int s[N];

int main()
{
	cin>>n>>m;
	for(int i = 1; i <= n; i ++ ){
		cin>>s[i];
		for(int j = 1; j <= s[i] ; j ++ ){
			cin>>v[i][j]>>w[i][j];
		}
	}
	
	for(int i = 1; i <= n; i ++ ){//i代表第幾種物品
		for(int j = m; j >= 0 ;j -- ){//j代表所給的空間
			for(int k = 1 ; k <= s[i]; k ++ ){//k代表第i種物品的第k個
				if(j >= v[i][k]){
					f[j] = max(f[j], f[j - v[i][k]] + w[i][k]);
				}
			}
		} 
	} 
	cout<<f[m]<<endl;
	return 0;
}