JZ初中OJ 2267. 宝物筛选

题目描述

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

输入

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

输出

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

样例输入

样例输出

数据范围限制

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