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

时间：2022-06-13 22:17:49

题目链接：https://www.luogu.org/problemnew/show/P1757#sub

题目描述

自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

分组背包的模板题

#include <bits/stdc++.h>

using namespace std;

int main()

{

    int n, m;

    cin >> m >> n;

    int dp[];

    int w[][], val[][], ord[];

    int cur = ; int a, b, c; int maxk = ;

    for (int i = ; i <=n; i++)

    {

        cin >> a >> b >> c;

        maxk = max(maxk, c);          //记录下组数的最大值，方便循环的时候定义边界

        ord[c]++;                     //第c组的第几个物品

        w[c][ord[c]] = a;             //第几组第几个物品的重量

        val[c][ord[c]] = b;

    }

    for(int k=;k<=maxk;k++)               //第k组

        for (int j = m; j >= ; j--)       //背包容量

        {

            for (int i = ; i <= ord[k]; i++)     //该组的物品序号

            {

                if(j>=w[k][i])     //由于j的范围是定义为>=0的，所以要记得加上这一条语句

                    dp[j] = max(dp[j], dp[j - w[k][i]] + val[k][i]);

            }

        }

    cout << dp[m] << endl;

    return ;

}

2018-05-16

相关文章