【洛谷】P1757 通天之分组背包**（分组背包）

穿越隧道

还是数组模拟快。
通过数组模拟，来找到有多少组。
每组有哪几样背包，每个背包的体积和价值是咋样的。

#include <bits/stdc++.h>
using namespace std;
const int N = 1e3 + 10;
int s[N];
int v[N][N],w[N][N];
int f[N];
int n,m;
int a,b,c;
unordered_map<int,int> mp;//统计有多少组 
int d[N];
int main(){
cin >> m >> n;
int group = 0;
for(int i = 1; i <= n; i++){
cin >> a >> b
>> c;
group = max(group,c);//最多有多少组 
d[c]++;
v[c][d[c]] = a;
w[c][d[c]] = b;
}
for(int i = 1; i <= group; i++){
for(int j = m; j >= 0; j--){
for(int k = 1; k <= d[i]; k++){
if(v[i][k] <= j){
f[j] = max(f[j], f[j - v[i][k]] + w[i][k]);
}
}
}
}
cout << f[m] << endl;
return 0;
}

该代码在洛谷第5个测试点超时，洛谷显示得99分。
map和unordered_map都是同样的超时和相同的得分。

#include <bits/stdc++.h>
using namespace std;
const int N = 1e3 + 10;
int s[N];
int v[N][N],w[N][N];
int f[N];
int n,m;
int a,b,c;
unordered_map<int,int> mp;//统计有多少组 
int main(){
cin >> m >> n;
for(int i = 1; i <= n; i++){
cin >> a >> b
>> c;
mp[c]++;
v[c][mp[c]] = a;
w[c][mp[c]] = b;
}
for(int i = 1; i <= (int)mp.size(); i++){
for(int j = m; j >= 0; j--){
for(int k = 1; k <= mp[i]; k++){
if(v[i][k] <= j){
f[j] = max(f[j], f[j - v[i][k]] + w[i][k]);
}
}
}
}
cout << f[m] << endl;
return 0;
}

最后

以上就是哭泣太阳为你收集整理的【洛谷】P1757 通天之分组背包**（分组背包）的全部内容，希望文章能够帮你解决【洛谷】P1757 通天之分组背包**（分组背包）所遇到的程序开发问题。

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