求一个公式或者算法

[posted by wap]

zzzz...看来没有最优算法了，还不如就无限穷举取最佳结果吧…我也玩蛋去了

这个好像没什么道理

感谢FOXfoO和离神最近的人，我尽快找人验证你们的思路。

你这个算法貌似不对啊
比如：3GB、3GB、1.5GB、1.5GB
按照你的算法，显然要刻成：(3)、(1.5+1.5)、(3)也就是3张盘
但实际上只需要(3+1.5)和(3+1.5)也就是2张盘

我怀疑你看懂沒啊
算了算了

好吧，其实各位都想复杂了，其实这个问题很简单的，
我能提供算法，但是不能保证最优，但是计算过程也十分简单。

首先，算法默认a[0].....a[n]均小于4.5

参数也就一个，就是文件大小，
首先对文件大小进行排序，
形成a[0]........a[n]

然后是一个递归调用

取一头一尾相加比较大小，
如果和小于4.5，之和再加上次头、次尾，

如同天平加砝码，
加码顺序按照先加头后加尾的方法


头1 + 尾1 < 4.5

头1 + 尾1 + 头2 < 4.5

头1 + 尾1 + 头2 + 尾2 < 4.5



可能出现情况：

头1 + 头2 + 尾1 < 4.5

头1 + 尾1 + 尾2 <4.5

数组中间不会产生间隔，总之就是一个掐头去尾的过程

我说没道理的原因是这样的，你看，你说：
“这样假设得到一个盘数i，然后把剩下的视频看能不能塞到这i个盘中，如果可以，OK，这已经是最优的了。”
这个所谓的“然后把剩下的视频看能不能塞到这i个盘中”里根本没算法，到底怎么来看能不能“把剩下的视频看能不能塞到这i个盘中”呢？
所以我说没道理。

你们都很蛋疼,楼主蛋最疼,算了,我去玩蛋了

500M-2.3G，楼主是在备份爱情动作片吧。。。

第一步是对的，后面就点点点...

3, 1.5, 1.5, 1.5, 1.4, 0.1

唉。。。递归啊
剩下的一样是递归啊

楼主的问题只是一维组合

还有二维组合，假设好几块停车场，停大大小小的车辆

还有三维组合，几个箱子，放各种各样的球体（或者立方体，或者任意形状的物体）

这些都是一个类别的问题

请解释一下你的办法
假设数列是这样子的六个文件：
2.27, 2.26, 1.127,1.126, 0.1, 0.1

这就是装箱问题啊
线性规划

http://www.zhuangxiang.com/
软件一个 装箱大师

类似的
自己转换成你的问题用吧

请问若有一个富翁拥有十份不同价值的产业，每份产业都不可再分割，他的两个儿子继承遗产，该如何分配？会计员，请给机器输入一组十个不同的随机数。

将你需要刻录的文件大小代入第一个数组（有注释语句的），然后在WEB环境下运行，会输出分组方法。

不过根据网友的数据例子这不是最优算法。

我想最优算法只有穷举了。

穷举+1.....

穷举的思路我有，但实际上写不来~~~

穷举不用思路的吧，反正都是举那么多次？

有N个数，放到数组里。
需要：
任意一个数的值
任意两个数之和的值
任意三个数之和的值
任意四个数之和的值
……
任何N-1个数之和的值
超过4.5G的直接删除
然后挑出一组等于或小于4.5但最大的数，将其输出，且从数组中剔除。
新形成的数组再进行一次如上操作，直到数组清空。

我觉得思路就是这样的，但不知道怎么写~~~

穷举的复杂度是N的N次方， 想想有100个文件。。。。。。。

100个文件，以组合论，有：
1.26765060023E+30
种可能性~~~
穷举就算了~~~还是用我的算法，虽然不是最优，但基本上也满足需要了~~~

设t[1],t[2],t[3],t[4],t[5],t[6]等于您说的上述数值，

t[1] + t[6] < 4.5

t[1] + t[2] + t[6] > 4.5

退回

t[1] + t[6] + t[5] = 4.5

符合条件，第一张光盘内容：t[1],t[6],t[5]

此时序列剩下,t[2],t[3],t[4]

t[2] + t[4] < 4.5

t[2] + t[4] + t[3] = 4.5

符合条件，第二张光盘内容： t[2],t[3],t[4]

从大到小排列，注意我说的两点内容，掐头去尾，先比头再比尾，谢谢~~~

欢迎提供特殊数据来验证我的想法，而且运行效率应该也是最高的，比算组合啥的应该快多了~~~高手应该能够写出程序了

:D :D :D

有N个数，放到数组X，记为X1,X2,...,Xn。
有M个非空容器记为R1,R2...Rm。

*将Xj放进Rk中或者放进一个新容器，并从数组中删除。

检查是否现在数组为空。
1. 是。记录这组答案以及m，并且K++。
2. 否。j++，重复*步骤。

我计算机知识有限，不知道这个迭代描述的是否清楚

明白你的算法了，我又来举反例了

3, 1.5, 0.8, 0.8, 0.8, 0.8, 0.8, 0.5

[本帖最后由 qxch 于 2008-8-13 11:44 编辑]

R1、R2……Rm这些非空容器是怎么初始化的？

不用验证了，这种算法不对的。

一开始非空容器R数量为0。

X1的时候，程序会生成一个新容器，把X1放进去。这就是非空容器R1

*将Xj放进Rk中或者放进一个新容器
问题是新容器的容积是有限的，这样不行的，你这个思路和我第一个程序的思路是一样的。

不解。

新容器指4.5G的新盘，容积相对于文件是足够大的吧

3 + 0.5 + 0.8 = 4.2 [1]

1.5 + 0.8 + 0.8 + 0.8 = 3.9 [2]

0.8 [3]

您这组数据举的不蛮好哦~~~:D :D :D

X1/X2->R1
X3->R2
如何保证X1/X2->R1是最优解呢？
我的第一个算法是从大到小往容器里装，装不下为止，然后删除装好的，再来一遍~~~这样的算法通不过你提的那个200M*23的数据

我那个思路是穷举法

最优解是：
3, 1.5, = 4.5
0.8, 0.8, 0.8, 0.8, 0.8, 0.5 =4.5

穷举法的话就必须列举所有的组合，然后再在其中挑出符合要求的组合。
如果是100张盘，第一次计算的组合数量就是我上面给出的1.26+E30~~~

穷举100个数的排列就怕栈溢出。。。不过如果文件里有些大文件的话可以很快排除掉大批组合

其实lz这个问题的最优只不过是用的盘数最少，盘数相同的情况下剩余空间的大小没有多少意义

[本帖最后由 Nothing 于 2008-8-13 12:22 编辑]

嗯，计算的数量确实是天文数字，但是我这个思路是可以写出算法让计算机慢慢耗的

兄台明鉴，

此算法在样本足够多，且符合均匀线性分布或者近似于均匀线性分布的情况下是比较接近最优解的，
但确实不适用于离散性较大的样本............谢谢~~

不过就个人应用来说，应该还是足够了.......:D :D :D

盘数相同的情况下剩余空间必然相同

运筹学的东西都忘了 还是请数学家来吧

没什么特别的算法。
就是搜索，深度优先。
只能在搜索的基础上优化。

刚刚在大专班上学了数列的极限....但是,我不会......

把思路都交给我编程的朋友让他来实现，要换广告了，最后MARK下。弄出来东西再找人发礼品。

苹果上的刻录软件这方面很强，所有文件往里一拽，需要几张碟就算出来了