洛谷1757通天之分组背包

116 阅读 0 评论 77 点赞

我是靠谱客的博主眯眯眼酒窝，这篇文章主要介绍洛谷1757通天之分组背包，现在分享给大家，希望可以做个参考。

题目背景

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

题目描述

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

输入输出格式

输入格式：

两个数m,n，表示一共有n件物品，总重量为m

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

输出格式：

一个数，最大的利用价值

输入输出样例

输入样例#1：

复制代码

输出样例#1：

复制代码

1
2
10

说明

1<=m<=1000 1<=n<=1000 组数t<=100

思路：

分组背包入门题，没啥好说的～

代码：

复制代码

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
35
36
37
38
/*************************************************************************
> File Name: p.cpp
> Author: Zcy
> Mail: 296763002@qq.com
> Created Time: 三
1/23 18:16:17 2019
************************************************************************/
#include <stdio.h>
#include <algorithm>
#include <map>
#include <string.h>
#include <vector>
using namespace std;
vector<int>zcy[1005];
int v[1005], w[1005];
int dp[1050] = {0};
int main () {
int m, n, group;
scanf("%d%d", &m, &n);
for (int i = 1; i <= n; i++) {
scanf("%d%d%d", &v[i], &w[i], &group);
zcy[group].push_back(i);
}
for (int i = 1; i <= n; i++) {
if (!zcy[i].size()) break;
for (int k = m; k >= 0; k--) {
for (int j = 0; j < zcy[i].size(); j++) {
int vv = v[zcy[i][j]];
int ww = w[zcy[i][j]];
if (k - vv < 0) continue;
dp[k] = max(dp[k - vv] + ww, dp[k]);
}
}
}
printf("%dn", dp[m]);
return 0;
}