题目内容

P1757

大意:多组物品,每组中只能选一个,求最大价值

解题思路

一个裸的分组背包,只需每组分别枚举,然后统计答案即可,这里存储每组物品的数据使用的是 vector 和 pair 配合。

注意枚举物品的循环要在枚举容量的循环之内,因为每组中只能取一个物品,所以每次都只找出每组中对应容量选哪个物品能达到最大。就是一层一层的枚举组数,然后开始从大到小枚举容量(否则会重复),再然后枚举这一对应容量只选一个物品能达到的最大价值。

#include <cstdio>
#include <vector>
#include <utility>

std::vector<std::pair<int,int> > group[102];//group[i][j] 表示第 i 组中第 j 个物品
//pair 的第一个元素是重量,第二个元素是价值
int m,n,f[1005];

inline int max(int a,int b)
{
    return a>b?a:b;
}

int main()
{
    scanf("%d %d",&m,&n);
    for(int i=1;i<=n;i++)
    {
        int a,b,c;
        scanf("%d %d %d",&a,&b,&c);
        group[c].push_back(std::make_pair(a,b));
    }
    for(int k=0;k<102;k++)
        if(!(group[k].size()))
            continue;
        else
            for(int j=m;j>=0;j--)
                for(auto i:group[k])
                    if(j>=i.first)//要防止数组越界
                        f[j]=max(f[j],f[j-i.first]+i.second);
    printf("%d\n",f[m]);
    return 0;
}
最后修改日期:2020年3月1日

作者

留言

撰写回覆或留言

发布留言必须填写的电子邮件地址不会公开。