题目及翻译

题面

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

输入

两个数m，n，表示一共有n件物品，总重量为m。
接下来n行，每行3个数ai，bi，ci，表示物品的重量，利用价值，所属组数
1≤n,m≤1000

输出

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

输入样例

45 3
10 10 1
10 5 1
50 400 2

输出样例

10

题目思路

1.显然是一题01背包，题目都说了(笑。之前没怎么做过分组背包，想到了先遍历分组，却没想到先遍历空间(平常01背包图个方便，先遍历物品写习惯了 )，偷偷瞟了眼题解，豁然顿悟。在01背包的基础上，只要先遍历空间再遍历物品，就可以做到每个分组的每个物品只用一遍。

注意事项

1.先遍历空间的情况下要注意下标判负
2.分组可以直接开数组，我比较喜欢用stl库罢了。

AC代码

C/C++(代码几乎没有变更)

用时41MS 内存628K 长度805B

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MAXN(1e3 + 10),MAXM(1e3 + 10),INF(0x3f3f3f3f3f3f3f3f),MOD(9973);
struct node{
ll v,w;
node(ll v_ = 0,ll w_ = 0):v(v_),w(w_){
}
};
ll t,n,m,k,a,b,c,d,u,space,blank,flag,cnt,cur,sum,res;
ll dp[MAXN];
map<ll,vector<node> >mp;
void init() {
res = 0;
return;
}
ll check() {
return 0;
}
void bag() {
for(auto i:mp){//遍历分组
for(ll j=n;j>=0;j--){//遍历空间
for(auto k:i.second){//遍历物品
if(j < k.v)continue;//下标判负
dp[j] = max(dp[j],dp[j-k.v] + k.w);
}
}
}
}
void preProgram() {
return;
}
void solve() {
init();
for(ll i=0;i<m;i++){
cin>>a>>b>>c;
mp[c].push_back(node(a,b));
}
bag();
cout<<dp[n]<<endl;
return;
}
int main() {
preProgram();
cin>>n>>m;
solve();
return 0;
}

本文作者 CSDN@扶她小藜
个人主页链接 https://blog.csdn.net/weixin_44579869

最后

以上就是健康白云为你收集整理的洛谷 P1757 通天之分组背包（分组背包）[C,C++]题目及翻译题目思路注意事项AC代码的全部内容，希望文章能够帮你解决洛谷 P1757 通天之分组背包（分组背包）[C,C++]题目及翻译题目思路注意事项AC代码所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。