[已解决]【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

n m
a1 a2 ... a n
v1 w1
v2 w2
...
vm wm

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

输入样例

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

输出样例

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

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

#include<bits/stdc++.h>
using namespace std;
#define v(i) v[i].first
#define w(i) v[i].second
bool cmp(pair<int,int> a,pair<int,int> b)
{
        double avea=((double)a.second/(double)a.first);
        double aveb=((double)b.second/(double)b.first);
        return  avea==aveb?(a.first<b.first):avea>aveb;
}
int main()
{
        int n,m;
        cin>>n>>m;
        int a[250];
        pair<int,int> v[250];
        for(int i=0;i<n;i++)cin>>a[i];
        for(int i=0;i<m;i++)cin>>v(i)>>w(i);
        sort(v,v+m,cmp);
        //for(int i=0;i<m;i++)cout<<v(i)<<" "<<w(i)<<" "<<(double)w(i)/(double)v(i)<<"\n";
        //开始装包!
        int b[250];
        int ans=0;
        memset(b,0,sizeof(b));
        for(int i=0;i<n;i++)
        {
                for(int j=0;j<m;j++)
                {
                        while(a[i]>=v(j))
                        {
                                a[i]-=v(j);
                                b[i]+=w(j);
                        }
                }
                ans+=b[i];
        }
        cout<<ans;
        return 0;
}

跳转到最佳答案楼层

学习编程中的Ben

顶顶顶~

sfqxx

顶·

高山

哈哈哈哈哈

ExiaGN001

多重背包？

zhangjinxuan

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

多个完全背包……

ExiaGN001

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

#include<bits/stdc++.h>
using namespace std;
#define v(i) v[i].first
#define w(i) v[i].second
bool cmp(pair<int,int> a,pair<int,int> b)
{
        double avea=((double)a.second/(double)a.first);
        double aveb=((double)b.second/(double)b.first);
        return  avea==aveb?(a.first<b.first):avea>aveb;
}
int main()
{
        int n,m;
        cin>>n>>m;
        int a[250];
        pair<int,int> v[250];
        for(int i=0;i<n;i++)cin>>a[i];
        for(int i=0;i<m;i++)cin>>v(i)>>w(i);
        sort(v,v+m,cmp);
        //for(int i=0;i<m;i++)cout<<v(i)<<" "<<w(i)<<" "<<(double)w(i)/(double)v(i)<<"\n";
        //开始装包!
        int b[250];
        int ans=0;
        memset(b,0,sizeof(b));
        for(int i=0;i<n;i++)
        {
                for(int j=0;j<m;j++)
                {
                        while(a[i]>=v(j))
                        {
                                a[i]-=v(j);
                                b[i]+=w(j);
                        }
                }
                ans+=b[i];
        }
        cout<<ans;
        return 0;
}