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

142 阅读 0 评论 94 点赞

我是靠谱客的博主哭泣太阳，这篇文章主要介绍【洛谷】P1757 通天之分组背包**（分组背包），现在分享给大家，希望可以做个参考。

穿越隧道

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

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#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都是同样的超时和相同的得分。

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#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;
}