华师一附中OI组

标题: P1794 装备运输 [打印本页]
作者: admin    时间: 2018-6-29 18:28
标题: P1794 装备运输
https://www.luogu.org/problemnew/show/P1794

题目描述
德国放松对英国的进攻后，把矛头指向了东边——苏联。1943年初，东线的战斗进行到白热化阶段。据可靠情报，90余万德国军队在库尔斯克准备发动浩大攻势。因此，朱可夫元帅要求你立即从远东的军工厂运输大量装备支援库尔斯克前线。列车司机告诉你，一趟列车最多可以容纳V体积的武器装备，但是你可能不能装满，因为列车承受不了那么大的重量，一趟列车最多可以承载C单位的重量。同时，军工厂仓库提供给你一份装备清单，详细记录了每件装备的体积、重量和火力。为了有效支援朱可夫元帅，你要找到一种方案，使得总火力值最大。

输入输出格式
输入格式：
第一行：V和G表示最大体积和重量。

第二行：N表示仓库有N件装备。

第三到N + 2行：每行3个数Ti Vi Gi表示各装备的火力值、体积和重量。

输出格式：
输出一个数，表示可能获得的最大火力值。

输入输出样例
输入样例#1：
6 5
4
10 2 2
20 3 2
40 4 3
30 3 3
输出样例#1：
50
说明
对于100%的数据，V,G,N≤500
作者: Scorpio    时间: 2018-7-15 13:25
  1. #include<iostream>
  2. using namespace std;
  3. int f[525][525],t[525],v[525],g[525];
  4. int m,i,j,k,vv,gg;
  5. int main()
  6. {
  7.     cin>>vv>>gg>>m;
  8.     for(i=1;i<=m;i++)
  9.         cin>>t[i]>>v[i]>>g[i];
  10.     for(i=1;i<=m;i++)
  11.         for(j=vv;j>=v[i];j--)
  12.             for(k=gg;k>=g[i];k--)
  13.                 f[j][k]=max(f[j-v[i]][k-g[i]]+t[i],f[j][k]);
  14.     cout<<f[vv][gg];
  15.     return 0;
  16. }

复制代码
作者: 张笑宇    时间: 2018-7-28 15:35
  1. #include<iostream>
  2. using namespace std;
  3. int maxv,maxm,n;///最大体积 质量,数量
  4. int i,j,k;
  5. const int mx=510;
  6. int t[mx],v[mx],m[mx],dp[mx][mx];
  7. int main()
  8. {
  9.     cin>>maxv>>maxm>>n;
  10.     for (i=1;i<=n;i++) cin>>t[i]>>v[i]>>m[i];
  11.     for (i=1;i<=n;i++)
  12.         for (j=maxv;j>=v[i];j--)
  13.             for (k=maxm;k>=m[i];k--)
  14.                 dp[j][k]=max(dp[j][k],dp[j-v[i]][k-m[i]]+t[i]);
  15.     cout<<dp[maxv][maxm];
  16.     return 0;
  17. }
复制代码
作者: 张笑宇    时间: 2018-7-28 15:36
二维费用背包
作者: 黄煦喆    时间: 2018-7-29 10:04
  1. #include<iostream>
  2. using namespace std;
  3. int G,V,n;
  4. int w[501],v[501],dp[501][501],t[501];
  5. int main()
  6. {
  7.     cin>>V>>G;
  8.     cin>>n;
  9.     for(int i=1;i<=n;i++)cin>>t[i]>>v[i]>>w[i];
  10.     for(int i=1;i<=n;i++)
  11.         for(int j=V;j>=v[i];j--)
  12.             for(int k=G;k>=w[i];k--)
  13.             dp[j][k]=max(dp[j][k],dp[j-v[i]][k-w[i]]+t[i]);
  14.     cout<<dp[V][G];
  15.     return 0;
  16. }
复制代码
作者: zhwang    时间: 2018-7-29 20:15
  1. #include<cstdio>
  2. #include<algorithm>
  3. using namespace std;
  4. int f[501][501];
  5. int V,G;
  6. int n;
  7. int h[501],v[501],m[501];
  8. int main()
  9. {
  10.         scanf("%d%d",&V,&G);
  11.         scanf("%d",&n);
  12.         for(int i=1;i<=n;i++)
  13.         {
  14.                 scanf("%d%d%d",&h[i],&v[i],&m[i]);
  15.         }
  16.         for(int i=1;i<=n;i++)
  17.         {
  18.                 for(int j=V;j>=v[i];j--)
  19.                 {
  20.                         for(int k=G;k>=m[i];k--)
  21.                         {
  22.                                 f[j][k]=max(f[j][k],f[j-v[i]][k-m[i]]+h[i]);
  23.                         }
  24.                 }
  25.         }
  26.         printf("%d",f[V][G]);
  27.         return 0;
  28. }
复制代码

突然发现自己只会写滚动了，好生尴尬啊
作者: ZMQ    时间: 2018-8-4 22:50
提示: 作者被禁止或删除 内容自动屏蔽



欢迎光临 华师一附中OI组 (http://hsyit.cn/) Powered by Discuz! X3.2