首页 > 代码库 > codevs1669 运输装备
codevs1669 运输装备
1669 运输装备
时间限制: 1 s
空间限制: 256000 KB
题目等级 : 钻石 Diamond
题目描述 Description
德国放松对英国的进攻后，把矛头指向了东北——苏联。 1943年初，东线的站头进行到白热化阶段。据可靠情报，90余万德国军队在库尔斯克准备发动好大的攻势。因此，朱可夫元帅要求你立即从远东的军工厂运输大量装备支援库尔斯克前线。 列车司机告诉你，一趟列车最多可以容纳V体积的武器装备，但是你可能不能装满，因为列车承受不了那么大的重量，一趟列车最多可以承载G单位的重量。同时，军工厂仓库提供给你一份装备清单，详细记录了每件装备的体积、重量和火力。为了有效支援朱可夫元帅，你要找到一种方案，使得总火力值最大。
输入描述 Input Description
第一行：V和G表示最大重量和体积。 第二行：N表示仓库有N件装备； 第三到N+2行：每行3个数Ti Vi Gi表示个装备的火力值、体积和重量；
输出描述 Output Description
输出一个数，表示可能获得的最大火力值
样例输入 Sample Input
6 5
4
10 2 2
20 3 2
40 4 3
30 3 3
样例输出 Sample Output
50
数据范围及提示 Data Size & Hint
【数据范围】
对于50%的数据，V,G,N≤100
对于100%的数据，V,G,N≤1000
/*因为有体积和重量两个限制，所以多加一重循环 直选一次，所以倒序。 */#include <iostream>#include<cstdio>#include<cstring>using namespace std;int power[1000],weight[1000],shape[1000],f[1000][1000];int G,V,n;int main(){ cin >>V>>G>>n; for(int i=1; i<=n; i++) cin >> power[i]>>shape[i]>>weight[i]; for(int i=1; i<=n; i++) for(int j=G; j>=weight[i]; j--) for(int k=V; k>=shape[i]; k--) f[j][k]=max(f[j][k],f[j-weight[i]][k-shape[i]]+power[i]); cout << f[G][V]; return 0;}
codevs1669 运输装备
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。