纪中第四天(c组)(4)

时间:2021-11-10 11:59:49

题目

   终于,破解了千年的难题。小 FF 找到了王室的宝物室,里面堆满了无数价值连城的宝物……这下小 FF 可发财了,嘎嘎。但是这里的宝物实在是太多了,小FF 的采集车似乎装不下那么多宝物。 看来小 FF 只能含泪舍弃其中的一部分宝物了……小FF 对洞穴里的宝物进行了整理,他发现每样宝物都有一件或者多件。他粗略估算了下每样宝物的价值,之后开始   了宝物筛选工作:
        小 FF 有一个最大载重为 W 的采集车, 洞穴里总共有 n 种宝物的,每种宝物的价值为v [i], 重量为 w[i], 每种宝物有 m[i]件。 小 FF 希望在采集车不超载的前提下,选择一些宝物装进采集车,使得它们的价值和最大。

输入

      第一行为 2 整数 N 和 W,分别表示宝物种数和采集车的最大载重。
      接下来 n 行每行三个整数, 其中第 i 行第一个数表示第 i 类品价值, 第二个整数表示一件该类物品的重量, 第三个整数为该类物品数量。

输出

输出仅一个整数ans, 表示在采集车不超载的情况下收集的宝物的最大价值。

样例输入

4 20
3 9 3
5 9 1
9 4 2
8 1 3

样例输出

47

数据范围限制

对于 30%的数据: n <=  ∑m[i] <= 10^4; 0 <= W <=10^3.
对于 100%的数据: n <= ∑m[i] <=10^5; 0<= W <=4 * 10^4;
                            1 <= n <= 100.

思路

这是一道多重背包的典型模板题,对着代码抄即可。这题因为数据大,AC要用到优化,但由于本人是个辣鸡,所以只能打个最普通的代码了。

代码

#include<cstdio>
#include<iostream>
using namespace std;
int n,n1,f[40001],v[101],w[101],m[101];
int main()
{
    scanf("%d%d",&n,&n1);
    for(int i=1;i<=n;i++)
    scanf("%d%d%d",&v[i],&w[i],&m[i]);
    for(int i=1;i<=n;i++)
        for(int j=n1;j>=0;j--)
            for(int k=0;k<=m[i];k++)
                if(w[i]*k>j)
                    break;
                else
                    f[j]=max(f[j],f[j-k*w[i]]+k*v[i]);
    printf("%d",f[n1]);
    return 0;
}