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个回答

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

明显的背包问题变了个说法

Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!
立即提问
相关内容推荐