首页 诗词 字典 板报 句子 名言 友答 励志 学校 网站地图
当前位置: 首页 > 教程频道 > 开发语言 > C++ >

求解一路编程题!感兴趣者留步

2012-12-23 
求解一道编程题!感兴趣者留步最佳存储时间限制:1000 ms|内存限制:65536 KB 描述设有n 个程序{1,2,…, n }要

求解一道编程题!感兴趣者留步
最佳存储
时间限制: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,我打错了。
[解决办法]
大家帮帮忙啊

热点排行