[已解决]【C++板块提升计划】梦想护卫舰 第8关 鱼C旅行团【答题有奖】 【原创】

zhangjinxuan

上一关： 逃离荒岛

梦想护卫舰 第8关 鱼C旅行团 正常题型

修好零件出发没多久，小甲鱼 和 不二如是 坐着私人游艇赶了过来……

不二如是 见到我们之后，兴奋的说道：

”啊，勇敢的鱼油们，为了感谢你们救了我，我决定……“
”带你们去旅游！“

你们听到这个消息后，非常兴奋

可是小甲鱼说：

不过现在有一些问题，我们旅游不知道每个东西该带几个，因为我们的船是有限的，每个船的容积也可能不一样，而且这些东西，也各有各自的重量和价值……

题目

现在一共有 n 艘船可以用来装旅游所要带的物品，第 i 艘船的装载极限是 a_i，另外，还有 m 个物品，其中，第 i 个物品重量是 v_i，实际的价值是 w_i，不过好在，每个物品都有无穷个

请问，在每艘船不超重的情况下，能获得的最大价值是多少？

注意：当然不能用两艘船装一件物品

你能解决这个问题吗？

输入格式
第一行两个数字，分别表示 n, m
第二行 n 个数字，第 i 个数字也就是 a_i
接下来 m 行，每行两个数字，第 i 行内容分别是 v_i, w_i

1. n m
   
2. a1 a2 ... a n
   
3. v1 w1
   
4. v2 w2
   
5. ...
   
6. vm wm

复制代码

输出格式
一个数字，表示能获得的最大价值

输入样例

1. 1 5
   
2. 10
   
3. 5 3
   
4. 3 6
   
5. 7 8
   
6. 5 9
   
7. 2 4

复制代码

输出样例

1. 20

复制代码

数据范围
所有数据 <= 200

其他说明
题目、题解为个人原创，时间限制 1s，空间限制 256mb

                               
登录/注册后可看大图

答案与解析

游客，如果您要查看本帖隐藏内容请回复

[/hide]
下一篇：https://fishc.com.cn/forum.php?mod=viewthread&tid=223520
最佳战士排行榜

	第一名	第二名	第三名
名字	ExiaGN001	等待着勇敢细心聪明的鱼油~
链接	戳我
代码得分	100
综合评分	100
奖励	鱼币荣誉共8个+最佳答案	鱼币荣誉共8个	鱼币荣誉共4个

如果你喜欢，别忘了评分

最佳答案

月排行榜 / 总排行榜

ExiaGN001

2023-1-11 13:01:19

我的答案，请帮忙评测一下:

1. #include<bits/stdc++.h>
   
2. using namespace std;
   
3. #define v(i) v[i].first
   
4. #define w(i) v[i].second
   
5. bool cmp(pair<int,int> a,pair<int,int> b)
   
6. {
   
7.         double avea=((double)a.second/(double)a.first);
   
8.         double aveb=((double)b.second/(double)b.first);
   
9.         return  avea==aveb?(a.first<b.first):avea>aveb;
   
10. }
    
11. int main()
    
12. {
    
13.         int n,m;
    
14.         cin>>n>>m;
    
15.         int a[250];
    
16.         pair<int,int> v[250];
    
17.         for(int i=0;i<n;i++)cin>>a[i];
    
18.         for(int i=0;i<m;i++)cin>>v(i)>>w(i);
    
19.         sort(v,v+m,cmp);
    
20.         //for(int i=0;i<m;i++)cout<<v(i)<<" "<<w(i)<<" "<<(double)w(i)/(double)v(i)<<"\n";
    
21.         //开始装包!
    
22.         int b[250];
    
23.         int ans=0;
    
24.         memset(b,0,sizeof(b));
    
25.         for(int i=0;i<n;i++)
    
26.         {
    
27.                 for(int j=0;j<m;j++)
    
28.                 {
    
29.                         while(a[i]>=v(j))
    
30.                         {
    
31.                                 a[i]-=v(j);
    
32.                                 b[i]+=w(j);
    
33.                         }
    
34.                 }
    
35.                 ans+=b[i];
    
36.         }
    
37.         cout<<ans;
    
38.         return 0;
    
39. }
    

复制代码

跳转到最佳答案楼层

学习编程中的Ben

顶顶顶~

sfqxx

顶·

高山

哈哈哈哈哈

ExiaGN001

多重背包？

zhangjinxuan

ExiaGN001 发表于 2023-1-11 12:48
多重背包？

多个完全背包……

ExiaGN001

我的答案，请帮忙评测一下:

1. #include<bits/stdc++.h>
   
2. using namespace std;
   
3. #define v(i) v[i].first
   
4. #define w(i) v[i].second
   
5. bool cmp(pair<int,int> a,pair<int,int> b)
   
6. {
   
7.         double avea=((double)a.second/(double)a.first);
   
8.         double aveb=((double)b.second/(double)b.first);
   
9.         return  avea==aveb?(a.first<b.first):avea>aveb;
   
10. }
    
11. int main()
    
12. {
    
13.         int n,m;
    
14.         cin>>n>>m;
    
15.         int a[250];
    
16.         pair<int,int> v[250];
    
17.         for(int i=0;i<n;i++)cin>>a[i];
    
18.         for(int i=0;i<m;i++)cin>>v(i)>>w(i);
    
19.         sort(v,v+m,cmp);
    
20.         //for(int i=0;i<m;i++)cout<<v(i)<<" "<<w(i)<<" "<<(double)w(i)/(double)v(i)<<"\n";
    
21.         //开始装包!
    
22.         int b[250];
    
23.         int ans=0;
    
24.         memset(b,0,sizeof(b));
    
25.         for(int i=0;i<n;i++)
    
26.         {
    
27.                 for(int j=0;j<m;j++)
    
28.                 {
    
29.                         while(a[i]>=v(j))
    
30.                         {
    
31.                                 a[i]-=v(j);
    
32.                                 b[i]+=w(j);
    
33.                         }
    
34.                 }
    
35.                 ans+=b[i];
    
36.         }
    
37.         cout<<ans;
    
38.         return 0;
    
39. }
    

复制代码