Algorithm 的挑战

江田岛平八

巴士 -可载 30人

顾客A组-12人
顾客B组-28人
顾客C组-15人
顾客D组- 4人
顾客E组- 7人
顾客F组- 5人
顾客G组-22人

巴士的数量是无限的。
共有7组顾客，每一组的顾客都不要和同组的人分开坐。

怎样在用最少辆巴士的情况下把这些顾客都载出去？？
重点在尽量把前面的巴士挤满人，就算最后1辆巴士只载1个人也没关系。

欢迎pseudocode或语言解释。

[ 本帖最后由 江田岛平八 于 23-10-2007 09:00 PM 编辑 ]

为人民服务

这也叫Algorithm挑战？
用两个Loop就搞定.

江田岛平八

原帖由 为人民服务 于 23-10-2007 09:37 PM 发表
这也叫Algorithm挑战？
用两个Loop就搞定.

不如你和大家分享一下。

江田岛平八

上面那些只是例子。

再说详细点吧。

巴士的载人量=30
巴士的数量=无限。
顾客组的数量=1到无限。
每1组顾客的数量=1 到 巴士的载人量

[ 本帖最后由 江田岛平八 于 23-10-2007 11:09 PM 编辑 ]

tensaix2j

如果outcome重要过processing time的话，可以来个brute force..
毕竟这里只有七组人，最maximum 只有7! ＝5040 种排法。。
然后就跟排法塞进巴市就可以了。。

江田岛平八

原帖由 SotongJiang 于 24-10-2007 01:42 AM 发表
因为没有严格数学证明的缘故，我的想法有点*龙头蛇尾*，如下，莫见笑：
先SORT组别的人数，由大到下，就成了(表1)：
GROUP    NoOfPpl     30-NoOfPpl
=====    =======     ==========
B        28        ...

这方法不错，我又学到新东西了。

但就不大适合解决这问题。
因为1辆巴士最多是有可能载30组顾客。（每1组顾客只有1人，所以共30组）
因为1辆巴士最少是有可能载1组顾客。（单1组顾客就有有30人了）

江田岛平八

原帖由 tensaix2j 于 24-10-2007 09:22 AM 发表
如果outcome重要过processing time的话，可以来个brute force..
毕竟这里只有七组人，最maximum 只有7! ＝5040 种排法。。
然后就跟排法塞进巴市就可以了。。

那个“！”是Factoria 吗？？太久没教书了。Paiseh......
我有想过用尽所有Premutation的方法，但用太多Executing Cost了，不太符合efficiency。
而且顾客组的数量是由1到Infinity的。用Infinity又好像没有什么说服力。 总之顾客组的数量可以是任何Positive的数字。

[ 本帖最后由 江田岛平八 于 27-10-2007 03:55 AM 编辑 ]

tensaix2j

那你可能要参考
genetic algorithn, hill.climbing, simulated.annealing 等等algorithms 了。。

megablue

1. //to store list of buses with free sit(s)
   
2. $freeBusList = new List();
   
3. $groups->orderByDesc('total_passenger');
   
4. 
   
5. while($groupIterator = $groups->getIterator())
   
6. {
   
7.    //check the list for nearest match, if no bus in the list matched, get a new bus
   
8. 
   
9.    if(!$bus = $freeBusList->getNearestFit($groupIterator->group->totalPassenger())
   
10.    {
    
11.       $buses[] = $bus = new Bus();
    
12.    }
    
13. 
    
14.    //get passenger out of the group
    
15.    while($passenger = $groupIterator->group->getPassenger())
    
16.    {
    
17.         //push the passenger into the bus
    
18.         $bus->insert($passenger);
    
19. 
    
20.         //if he is the passenger
    
21.         if($passenger->isLast())
    
22.         {
    
23.                 $number_of_freesit = $bus->getFreeSit();
    
24.                 if($number_of_freesit > 0)
    
25.                 {
    
26.                         $freeBusList->insertBus($bus, $number_of_freesit);
    
27.                 }
    
28. 
    
29.                 //to make sure passenger from the same group are together.
    
30.                 $groupIterator->next();
    
31.         }
    
32.    }   
    
33. }

复制代码

[ 本帖最后由 megablue 于 27-10-2007 08:55 PM 编辑 ]

pony

我想到一个方式，效率不是最高，不过蛮简单的。
1. 先把顾客组循序排列。
2. 把人数最多的先放进巴士。
3. 把人数最多又少过剩余位子的顾客组放进巴士。
4. 重复第 3. 步骤直到没有没有任何顾客组可以放进巴士。
5. 换巴士，然后回到第 2. 步骤，直到所有的顾客都放进巴士了。