一个实用的计算问题

mcmay

各位新年好，我今天碰到一个很实际的计算问题，想问问各位该如何用C代码实现较好。问题是这样的，我有十个电影文件，其大小分别为(以G为单位）：

1.37,1.36,1.53,1.36,0.335,1.47,1.36,1.57,1.36,1.36

总大小约13.1G 我想把它们分别刻到3张DVD数据碟中，每个碟的可刻录容量为4.4G，我做了很多分配大小的手动试验都以失败告终，后来想到用程序来实现分配，不过不知如何做到，写了一两个代码都不尽如人意，不知是事实上确实无法做到，还是我的算法有问题，故请各位看看这个实际问题该如何用C代码实现为好，谢谢！

langue

还真找到了，Google 强大，Wikipedia 光荣

http://forums.sun.com/thread.jspa?threadID=5260768
http://en.wikipedia.org/wiki/Bin_packing_problem

雨过白鹭洲

这个问题就不该用C代码来实现

如果不考虑分割电影的话，3张碟估计是不够的

langue

原帖由 雨过白鹭洲 于 2009-2-14 16:49 发表
这个问题就不该用C代码来实现

如果不考虑分割电影的话，3张碟估计是不够的

这跟 C 有啥特别的关系不？
明明就是个 best fit algorithm，具体用哪种语言实现是另一码事 :wink:

http://www.google.com/search?q=best+fit+algorithm

不一定找得到确切结果，但应该有所启发。

mcmay

我的一个解法是：
CD 1: 1.36, 1.36, 1.36, 0.335
CD 2: 1.36, 1.47. 1.53
CD 3: 1.36, 1.37, 1.57

这里需要说明的是我把文件组合的最大值4.4G改大了一点点到4.5G，这样也不会超过一个DVD数据碟的容量。

我用了两个代码的结果相结合的方法，虽然仍然有点笨了，但还是解决了。
第一代码，将十个文件均拆分为四个一组的：

/* calc_x */

#include <stdio.h>

#define SIZE 10
#define MAX 4.5
#define MIN 4.3

int main(void){
   
    float ar[SIZE] = {1.37,1.36,1.53,1.36,0.335,1.47,1.36,1.57,1.36,1.36};
    float w,x,y,z;
    int g,j,k,m;
   
    for(g = 0; g < SIZE; g++){
        w = ar[g];
        for(j = 0; j < SIZE; j++){
            x = ar[j];
            for(k = 0; k < SIZE; k++){
                y = ar[k];
                for(m = 0; m < SIZE; m++){
                    z = ar[m];
                    if(w <= 1.57&&x <= 1.57&&y <= 1.57&&z <= 1.57 &&
                       w >= .335&&x >= .335&&y >= .335&&z >= .335 &&
                      (w+x+y+z)> MIN && (w+x+y+z) <= MAX){
                           printf("\nw = %g, x = %g, y = %g, z = %g",w,x,y,z);
                      }
                     
                 }
             }
         }
      }
    puts("\nDone!");
    getch();
    return 0;
}

在这个代码的结果中，我们可以发现，这样拆分是无法顾及到1.47，1.53和1.57这样的“大数”的，然后我想到了三个一包，代码如下：

#include <stdio.h>

#define SIZE 10
#define MAX 4.5
#define MIN 4.3

int main(void){
   
    float ar[SIZE] = {1.37,1.36,1.53,1.36,0.335,1.47,1.36,1.57,1.36,1.36};
    float w,x,y;
    int g,j,k,m;
   
    for(g = 0; g < SIZE; g++){
        w = ar[g];
        for(j = 0; j < SIZE; j++){
            x = ar[j];
            for(k = 0; k < SIZE; k++){
                y = ar[k];
                    if(w <= 1.57&&x <= 1.57&&y <= 1.57&&
                       w >= .335&&x >= .335&&y >= .335&&
                      (w+x+y)> MIN && (w+x+y) <= MAX)
                         printf("\nw = %g, x = %g, y = %g",w,x,y);                     
             }
         }
      }
    puts("\nDone!");
    getch();
    return 0;
}

在这个代码的结果中，我们仍然找不到1.57的影子。不过这不是问题了，因为我可以在三个一包和四个一包的拆分结果中找到符合实际的两包，剩下的就是第三包，而第三包也不超过DVD碟的上限。

gawk

tar10个电影文件成一个文件，然后用split命令的把tar文件按照你大小分一下

samon_fu

就几个文件，有啥好算的，刻碟的时候手动选着刻不就完了，就那几个文件，一瞪眼就完事了。