洛谷1757通天之分组背包

题目背景

直达通天路·小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

说明

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

思路：

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

代码：

/*************************************************************************
> 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;
}

转载请注明出处！！！

如果有写的不对或者不全面的地方 可通过主页的联系方式进行指正，谢谢

最后

以上就是眯眯眼酒窝为你收集整理的洛谷1757通天之分组背包的全部内容，希望文章能够帮你解决洛谷1757通天之分组背包所遇到的程序开发问题。

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