【C++板块提升计划】梦想护卫舰 第8关 鱼C旅行团【答题有奖】 【原创】
本帖最后由 zhangjinxuan 于 2023-1-16 11:05 编辑上一关： 逃离荒岛
梦想护卫舰 第8关 鱼C旅行团 正常题型
修好零件出发没多久，小甲鱼 和 不二如是 坐着私人游艇赶了过来……
不二如是 见到我们之后，兴奋的说道：
”啊，勇敢的鱼油们，为了感谢你们救了我，我决定……“
”带你们去旅游！“
你们听到这个消息后，非常兴奋
可是小甲鱼说：
不过现在有一些问题，我们旅游不知道每个东西该带几个，因为我们的船是有限的，每个船的容积也可能不一样，而且这些东西，也各有各自的重量和价值……
题目
现在一共有 n 艘船可以用来装旅游所要带的物品，第 i 艘船的装载极限是 ai，另外，还有 m 个物品，其中，第 i 个物品重量是 vi，实际的价值是 wi，不过好在，每个物品都有无穷个
请问，在每艘船不超重的情况下，能获得的最大价值是多少？
注意：当然不能用两艘船装一件物品
你能解决这个问题吗？
输入格式
第一行两个数字，分别表示 n, m
第二行 n 个数字，第 i 个数字也就是 ai
接下来 m 行，每行两个数字，第 i 行内容分别是 vi, wi
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
static/image/hrline/1.gif
答案与解析
**** Hidden Message *****
下一篇：https://fishc.com.cn/forum.php?mod=viewthread&tid=223520
最佳战士排行榜
|第一名|第二名|第三名
名字|ExiaGN001|等待着勇敢细心聪明的鱼油~|
链接|戳我||
代码得分|100||
综合评分|100||
奖励|鱼币荣誉共8个+最佳答案|鱼币荣誉共8个|鱼币荣誉共4个
如果你喜欢，别忘了评分{:10_254:} 顶顶顶~ 顶·{:10_256:} 哈哈哈哈哈 多重背包？ ExiaGN001 发表于 2023-1-11 12:48
多重背包？
多个完全背包…… 我的答案，请帮忙评测一下:
#include<bits/stdc++.h>
using namespace std;
#define v(i) v.first
#define w(i) v.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);
returnavea==aveb?(a.first<b.first):avea>aveb;
}
int main()
{
int n,m;
cin>>n>>m;
int a;
pair<int,int> v;
for(int i=0;i<n;i++)cin>>a;
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;
int ans=0;
memset(b,0,sizeof(b));
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
while(a>=v(j))
{
a-=v(j);
b+=w(j);
}
}
ans+=b;
}
cout<<ans;
return 0;
}
页:
[1]