求一个公式或者算法

我有若干500M到2.3G大小不等的MP4文件，想刻进若干容量为4.5G的刻录碟。当MP4文件的数量和每个影片的容量是确定的，求一个公式或者算法，可以算出来怎样把若干影片合在一起刻录才能使得耗费的刻录盘数量为最小。

在我找到答案之前给出答案的高人，赠送480P电影一套。

[本帖最后由 aironline 于 2008-8-8 09:46 编辑]

我玩蛋去

每个文件容量大小不等,根本不可能有固定公式可计算啊.楼主还不如把你所以文件以及容量列个表放上来,看看哪个蛋痛的的帮你计算下具体怎么刻

大小不等无非是参数A，参数B，参数C，只要参数可以确定，就可以找到公式计算。
如果我单只是把表列出来，就算有人排列出来，没有公式，一样不能证明他排列出来的就是最省碟的。

我也玩蛋去了

同玩蛋的路过~

[posted by wap]

以前想过要作这么个软件的…

我每次都是先放大文件，等超过容量了，删除1-2个替换成合适的小文件接近刻录盘的容量。这样剩下来越来越好分。楼主弄这么复杂干嘛

有算法，没公式。你找软件实力男吧……

嗯，有算法也行，就算是穷举式的，反正让电脑去忙活。

楼上哪位借个蛋给我玩玩.....

干吗 那你不是要录入所有片子的容量 然后开始算？
有这功夫 盘刻完2张了！

与其追求刻录盘数量为最小，不如把东西分好类，至少找着用着也方便

又疼了。。。。。。。。。。

所有片子的容量都录入好了，我是要批量刻盘的，追求的不是功夫，是成本。东西只有一类，就是电影。

很好！你很控哈！
帮你想想哈
不过我是写PHP的！

电影更要分了,或者按字母排序,或者按喜剧惊悚之类的剧情分类.否则随便乱数搭配,不知道刻到哪张盘上,你以后还打算再拿出来看么.

按剧情大类分一分，系列的话单独挑出来压一张，其他的就不打算分了。只要有目录，找起来没难度。

和谐社会

LZ蛋真疼啊...
自己用什么递归算法搞一下吧

什么意思

真谈疼！我竟然入了这个无聊的帖子！

8会

我都是随便凑到4G出头就刻了，刻录碟现在都这么便宜了，也不差那两三百M

LZ我用刻录盘换你的电影吧

四张刻录盘换一刻录盘电影，量大优惠。在没有一个公式或者算法之前我只能保证每张盘超过4.1G。

不能保证是最优算法。

[本帖最后由 FoxfoO 于 2008-8-8 14:15 编辑]

证明最优比提出算法还麻烦……

好办，用rar分卷打包，每个包4.5G，最高效率达成。。。。。

这个很简单啊
就是计算机里面的0-1背包问题
用动态规划就可以了
网上一搜一大堆

对啊 好NB 这才是王道啊 PFPF

求这个算法的使用方法

这就是光图办事的时候爽不考虑事后的方案，看的时候解包多么痛苦。

很简单，原理就由按容量由大到小往盘里放，放到哪个超过4.5G就换更小的一个，直到没有更小的。如此循环


程序也很好实现

把文件按大小降序排列，形成队列。做一个计数器。

步骤：
for 仍存在未标记文件{
计数器清零。
for （（文件编号=1 to 文件编号=末尾））
{
循环里的内容略，大致意思就是按文件由大到小读进来（只读未做标记的文件），计数器按文件容量自加。
如果计数器值小于4.5G，则将读入的文件做标记（标记也要建自加1的计数器，刻盘时标记数字一样的刻在一起）
如果计数器值大于4.5G，则再读下一个文件，直到队列末尾
}
}

[本帖最后由 上海狗狗 于 2008-8-8 16:01 编辑]

非最优。

3.0G , 0.9G, 0.5G, 0.2G*23

按照啸天的做法，会有
3.0+0.9+0.5=第一张碟
0.2*22=第二张碟
0.2=第三张碟

此种情况的最优解，应该为
3+0.9+0.2*3=第一张碟
0.2*20+0.5=第二张碟

所以从实用性来说上面，狗狗的那个简单可行，但从大到小排序读入这个思路根本上来说是有问题的

这个方案我已经用过了，不是最优的。

这个例子很好，很能说明问题。。。。。

不过你能给出通用算法么？

如果能，我昨天就写答案了...读书那几年，我就觉得我不会做这种需要思路缜密的题目。

如果lz把一个列表拿出来，或许还能做一个比较优的解，现在只能看着rar的解法感觉惊艳了

我操 我都说是01背包问题了楼主怎么还不去搜？

ls的太专业，我看晕了

我是在找解决问题的办法，不是在找解决“解决问题的办法”的办法。

LZ我可以用EXCEL帮你做出来.但是需要你自己输入数据

我想了一个...不过不会很好..我数学不行

先把所有的文件大小给存好.
然后把所有文件进行随机组合.
容量最接近4.8G(设定一个接近值比如4.7G)的就取出.没有再次随即排列.
取出之后循环.
只到排完所有文件...

RAR打包才是王道..233

你这个貌似和上海狗狗的算法一样额，应该不是最优排列。

RAR打包，还不如我直接把MP4文件切开。省事的多。

这是NP问题，在文件容量和数量不定的情况下，没有通用算法可以得出最优解的

我的算法是：
1，将文件按大小排序放入数组
2，从最大的那个文件开始遍历数组，并累计每个文件的大小
3，如果加入当前文件的容量后，总容量超过了4.5G，就将之前遍历过的文件放入需要存储列表中，同时将这些文件从文件列表中删除
4，跳到数组末尾，从最小的那个文件开始往前遍历数组，同样累计每个文件的大小
5，重复第3步
6，如果文件列表中还有剩余的文件，就将文件累计容量清0，回到第2步

这样应该可以保证最少碎片

01背包和楼主的问题区别还挺大

一个旅行者有一个最多能用m公斤的背包，现在有n件物品，它们的重量分别是W1，W2，...,Wn,它们的价值分别为C1,C2,...,Cn.若每种物品只有一件求旅行者能获得最大总价值。

这是01背包问题。因为楼主这没有价值这个参数，所以实际上就是求一张碟怎么能放最多的视频。
01背包求得是一次放置最优化
而楼主则是求用的是最少的碟。前几次最优化可能会造成后几次过于劣化，总体反而劣化。
举例

15个0.3g和15个4g的视频
若按01背包法，肯定是15个0.3放一张，然后15个4g15张，总共16张
实际上最优化的方法是每张一个4g一个0.3g总共15张

开始以为是价值和重量相等的01背包问题，仔细一看LZ原来是要刻多张盘口牙，不好意思我错了

提出一个思路：[理论上]
由于容量每盘只有4.5GB，所以将>2.25GB的视频全部挑出来，这些都是任何两个都不能塞在一张盘里的，必须分盘刻录。
这样假设得到一个盘数i，然后把剩下的视频看能不能塞到这i个盘中，如果可以，OK，这已经是最优的了。
如果塞不下，那么将剩下视频中大于1.125GB的视频全部挑出来，对上面这i个盘递归上述过程。一直到这i个盘全部塞不进去为止。
最后剩下的视频，也就是i个盘刻不下的，估计都是边角余料，OK，统统重新刻j个盘。
以上。
水平有限，可能是这样吧。