求解一道编程题!感兴趣者留步
最佳存储
时间限制:1000 ms | 内存限制:65536 KB
描述
设有n 个程序{1,2,…, n }要存放在长度为L的磁带上。若要存放程序i, 需要占用磁带的长度为Li,1<= i <= n。现在想请同学们设计一个存储方案,使得能够在磁带上存储尽可能多的程序。在保证存储最多程序的前提下还要求磁带的利用率达到最大。
输入
第一行为一个整数T,表示有T组测试数据。
对于每组测试数据,第一行是正整数L (不超过106),表示磁带的长度;第二行是正整数n (不超过100),表示有n个程序;第三行是n个正整数(每个数的数值不超过100),第i个数的数值Li表示存储它需要占用的磁带长度为Li,每个数用空格分开。
输出
对于每组测试数据,第一行是一个正整数,表示磁带能存储的最多程序个数;第二行是一个正整数,表示磁带存储的这些程序所占的总的磁带长度。
样例输入
1
60
10
2 3 8 10 12 13 16 21 23 80
样例输出
6
60
[解决办法]
贪心法。把最短的程序都挨个存下来就ok了。
[解决办法]
!
用贪心只能算出程序个数
L不超过106的话,还是用背包来递推好了
[解决办法]
磁带长度是不超过10的6次方,不是106,我打错了。
[解决办法]
大家帮帮忙啊