通天之分组背包(洛谷P1757 ）

题目背景

直达通天路·小 A 历险记第二篇

题目描述

自 01 背包问世之后，小 A 对此深感兴趣。一天，小 A 去远游，却发现他的背包不同于 01 背包，他的物品大致可分为 k 组，每组中的物品相互冲突，现在，他想知道最大的利用价值是多少。

输入格式

两个数 m,n，表示一共有 n 件物品，背包能承受的最大重量为 m。

接下来 n 行，每行 3 个数 ai​,bi​,ci​，表示物品的重量，利用价值，所属组数。

输出格式

一个数，最大的利用价值。

输入输出样例

输入 #1复制运行

45 3 10 10 1 10 5 1 50 400 2

输出 #1复制运行

10

说明/提示

0≤m≤1000，1≤n≤1000，1≤k≤100，ai​,bi​,ci​ 在int范围内。

/* //二维数组写法 #include <iostream> #include <vector> using namespace std; vector<vector<int>> w(101);//第i组第j件物品的重量 vector<vector<int>> v(101);//第i组第j件物品的利用价值 int dp[101][1001];//面对第i组物品 背包容量为j时的最大价值 int main(){ int m,n;//背包容量 物品件数 cin>>m>>n; for(int i=1;i<=n;i++){ int a,b,c; cin>>a>>b>>c; w[c].push_back(a); v[c].push_back(b); } for(int l=1;l<=100;l++){//遍历所有组 for(int i=1;i<=m;i++){//遍历背包容量 dp[l][i]=dp[l-1][i];//默认不选第l组物品 for(int j=0;j<w[l].size();j++){//遍历一组内所有物品 //可以选的时候比较选还时不选 if(i>=w[l][j]) dp[l][i]=max(dp[l][i],dp[l-1][i-w[l][j]]+v[l][j]); } } } cout<<dp[100][m]; return 0; } */ //一维数组写法 #include <iostream> #include <vector> using namespace std; vector<vector<int>> w(101);//第i组第j件物品的重量 vector<vector<int>> v(101);//第i组第j件物品的利用价值 int dp[1001];//背包容量为j时的最大价值 int main(){ int m,n;//背包容量 物品件数 cin>>m>>n; for(int i=1;i<=n;i++){ int a,b,c; cin>>a>>b>>c; w[c].push_back(a); v[c].push_back(b); } for(int l=1;l<=100;l++){//遍历所有组 for(int i=m;i>=0;i--){//遍历背包容量 要逆序 因为每个物品只能选择一次 for(int j=0;j<w[l].size();j++){//遍历一组内所有物品 //可以选的时候比较选还时不选 if(i>=w[l][j]) dp[i]=max(dp[i],dp[i-w[l][j]]+v[l][j]); } } } cout<<dp[m]; return 0; }