切换到宽版
  • 7108阅读
  • 3回复

如何解决这个问题 [复制链接]

上一主题 下一主题
离线edwing
 
只看楼主 倒序阅读 0 发表于: 2006-10-27
这是我生活中遇到的一个问题。

现在有n个大小文件(大小不尽相同),我要将它们刻录到光盘(每张光盘按650MB计算),为了节约光盘,怎么样将这些文件归类(即哪些文件放在一张光盘上,文件不能分割),使得需要的光盘总数最小。

输入数据:n(表示文件总数)
          i1
          i2
          ...
          in (文件的大小,长整型)
输出数据:s(需要的最少光盘数)
          f11 f12 f13 f14 1f5 ... (第一张光盘里的文件)
          f21 f22 f23 f24 ... (第二张光盘里的文件)
          ...
          fi1 fi2 fi3 ... (第i张光盘里的文件)

希望各位高手出手,小弟感激不尽。
离线swj05652
只看该作者 1 发表于: 2006-10-27
我感觉这是一个NP问题,很难解决的
可以考虑用一些近似算法,作出最优值
离线hexuefang
只看该作者 2 发表于: 2006-10-27
采用贪心算法,先将文件排序!
离线edwing
只看该作者 3 发表于: 2006-10-28
具体怎样做,看起来好像很简单,但我也想了很久都不知道有什么有效的算法。
快速回复
限100 字节
 
上一个 下一个