input:treasure.in output:treasure.out

时间限制: 1000 ms 空间限制: 60000 KB

题目描述

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

输入

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

输出

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

样例输入

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

样例输出

1
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.

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include<bits/stdc++.h>
using namespace std;
int v[4*10005],w[4*10005];
int f[4*10005];
int n,m,nl;
int main()
{
    freopen("treasure.in","r",stdin);
    freopen("treasure.out","w",stdout);
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        int x,y,s,t=1;
        cin>>y>>x>>s;
        while(s>=t)
        {
            v[++nl]=x*t;
            w[nl]=y*t;
            s-=t;
            t*=2;
        }
        v[++nl]=x*s;
        w[nl]=y*s;
    }
    for(int i=1;i<=nl;i++)
        for(int j=m;j>=v[i];j--)
            f[j]=max(f[j],f[j-v[i]]+w[i]);
    cout<<f[m];
}