嘉兴企业网站建设,asp技校网站,网站模块介绍,优猫券网站怎么做题目描述
终于#xff0c;破解了千年的难题。小 FF 找到了王室的宝物室#xff0c;里面堆满了无数价值连城的宝物。
这下小 FF 可发财了#xff0c;嘎嘎。但是这里的宝物实在是太多了#xff0c;小 FF 的采集车似乎装不下那么多宝物。看来小 FF 只能含泪舍弃其中的一部分…题目描述
终于破解了千年的难题。小 FF 找到了王室的宝物室里面堆满了无数价值连城的宝物。
这下小 FF 可发财了嘎嘎。但是这里的宝物实在是太多了小 FF 的采集车似乎装不下那么多宝物。看来小 FF 只能含泪舍弃其中的一部分宝物了。
小 FF 对洞穴里的宝物进行了整理他发现每样宝物都有一件或者多件。他粗略估算了下每样宝物的价值之后开始了宝物筛选工作小 FF 有一个最大载重为 W 的采集车洞穴里总共有 n 种宝物每种宝物的价值为 vi重量为 wi每种宝物有 mi 件。小 FF 希望在采集车不超载的前提下选择一些宝物装进采集车使得它们的价值和最大。
输入格式
第一行为一个整数 n 和 W分别表示宝物种数和采集车的最大载重。
接下来 n 行每行三个整数 ,,vi,wi,mi。
输出格式
输出仅一个整数表示在采集车不超载的情况下收集的宝物的最大价值。
输入输出样例
输入 #1复制
4 20
3 9 3
5 9 1
9 4 2
8 1 3
输出 #1复制
47
说明/提示
对于 30%30% 的数据≤∑≤104n≤∑mi≤1040≤≤1030≤W≤103。
对于 100%100% 的数据≤∑≤105n≤∑mi≤1050≤≤4×1040≤W≤4×1041≤≤1001≤n≤100。
#includeiostream
#includecstdio
#includecstdlib
#includestring
#includecstring
#includecmath
#includectime
#includealgorithm
#includeutility
#includestack
#includequeue
#includevector
#includeset
#includemap
using namespace std;
typedef long long LL;
const int N 2000, M 1e5;
int n, m;
int V[N], W[N];
int f[M];int main() {cin n m;int cnt 1;for (int i 1,v,w,s; i n; i) {scanf(%d%d%d, v, w, s);int k 1;while (s k) {V[cnt] v * k;W[cnt] w * k;s - k;k * 2;cnt;}if (s 0) {V[cnt] s * v;W[cnt] s * w;cnt;}}n cnt - 1;for (int i 1; i n; i) {for (int j m; j W[i]; j--) {f[j] max(f[j], f[j - W[i]] V[i]);}}cout f[m] endl;return 0;
}
