普通网友 2016-12-14 03:37 采纳率: 0%
浏览 886

ACM一道题 求大神给出思路或者代码 谢谢~~~~

Problem Description
CZJ的舍友请CZJ吃饭,作为舍友CZJ是不会放过吃穷舍友的机会,但自己身体又不好,不能吃太多也不能吃太少。假设每样食物都有一个饱腹度和价值,请你帮他算下刚好吃饱的情况下最多可以吃他舍友多少钱。
Input
第一行是一个T,代表数据的组数T(T≤100001)。每组两个整数p,y(1≤p≤1000,1≤y≤100),分别表示食物的数量和CZJ的饱腹度。
然后p个数Qpi表示第pi个食物的价值,之后p个数Mpi表示吃第pi个食物得到的饱腹度。(1≤Qpi≤10000,1≤Mpi≤1000)。
Output
对于每一个样例输出CZJ能吃下的最大价值。
Sample Input

1
5 100
11 6 7 5 6
40 50 60 20 30

Sample Output

18

Author
SCNU20102200088

  • 写回答

3条回答 默认 最新

  • Book1346 2016-12-14 04:05
    关注

    看完题目的第一想法,就是背包问题。T组则是解决T个背包问题。
    实际上每组的背包问题,还是很好解决的。
    感觉问题重点还是在于空间的优化上,以及大数据的计算优化上。
    还有不知道你是不是贴错题目了,1≤y≤100,然而1≤Mpi≤1000?
    如果真这样的话,那不表示Mpi大于100,直接排除这个食物?

    评论

报告相同问题?

悬赏问题

  • ¥15 数据库数据成问号了,前台查询正常,数据库查询是?号
  • ¥15 算法使用了tf-idf,用手肘图确定k值确定不了,第四轮廓系数又太小才有0.006088746097507285,如何解决?(相关搜索:数据处理)
  • ¥15 彩灯控制电路,会的加我QQ1482956179
  • ¥200 相机拍直接转存到电脑上 立拍立穿无线局域网传
  • ¥15 (关键词-电路设计)
  • ¥15 如何解决MIPS计算是否溢出
  • ¥15 vue中我代理了iframe,iframe却走的是路由,没有显示该显示的网站,这个该如何处理
  • ¥15 操作系统相关算法中while();的含义
  • ¥15 CNVcaller安装后无法找到文件
  • ¥15 visual studio2022中文乱码无法解决