吐槽
滚动

2017 C语言积分赛 热身赛 D题 帮助莉莉娅 题解

题目描述

题目背景
再过十几天,人类远征军就要出发去讨伐星神(visitor)了。
正规勇者莉莉娅·阿斯普雷伊及一众准勇者们正在为行军问题而焦头烂额。
“这么多的粮草,还有那么远的路,这该怎么办啊?”莉莉娅抱怨道。
你能帮帮莉莉娅吗?

题目描述
从皇都到达星神居住地将会消耗很多时间。
而为了保证军士们的生活,需要带上足够的粮草。
皇都共有n堆粮草可供选择,每堆粮草有重量p,体积q和价值w,而为了便于行军,莉莉娅只能选择不超过u重量且不超过v体积的粮草带走。

输入

第一行,包含三个正整数,分别为粮草数量n,最大载重量u,最大体积v。
接下来n行,每行包含三个正整数p[i]、q[i]和w[i]。
第i+1行的p[i]表示第i堆粮草的重量,q[i]表示第i堆粮草的体积,w[i]表示第i堆粮草的价值。

1<=n<=1000,1<=u<=1000,1<=v<=1000
所有数据不大于maxint

输出

一行,输出能载的粮草的最大价值。

样例输入

样例输出

马上就能看出贪心肯定跑不动,再稍加分析,发现是二维约束的01背包问题。

对于01背包问题,采取正向枚举数量,再反向枚举约束条件的做法。

Code:

 

Contents licensed under Creative Commons by-nc-sa 3.0.
Post Comment

Post Comment