纪中第四天（c组）（4）

题目

   终于，破解了千年的难题。小 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;
}