在有些情况下,完美是优秀的敌人。有时候,你只需找到一个能够大致解决问题的算法,此时贪婪算法正好可派上用场,因为它们实现起来很容易,得到的结果又与正确结果相当接近。
贪婪法是一种不追求最优解,只希望得到较为满意解的方法。贪婪法一般可以快速得到满意的解,因为它省去了为找最优解要穷尽所有可能而必须耗费的大量时间。
装箱算法简单描述如下:
{
输入箱子的容积;
输入物品种数n;
按体积从大到小顺序,输入各物品的体积;
已用箱子计数器box_count为0;
for (i=0;i<n;i++)
{ 从已用的第一只箱子开始顺序寻找能放入物品i 的箱子j;
if (已用箱子都不能再放物品i)
{ 另用一个箱子,并将物品i放入该箱子;
box_count++;
}
else
将物品i放入箱子j;
}
}
上述算法能求出需要的箱子数box_count,并能求出各箱子所装物品。下面的例子说明该算法不一定能找到最优解,设有6种物品,它们的体积分别为:60、45、35、20、20和20单位体积,箱子的容积为100个单位体积。按上述算法计算,需三只箱子,各箱子所装物品分别为:第一只箱子装物品1、3;第二只箱子装物品2、4、5;第三只箱子装物品6。而最优解为两只箱子,分别装物品1、4、5和2、3、6。
}
/////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////
//php实例
//物品
$items[0] = 60;
$items[1] = 45;
$items[2] = 35;
$items[3] = 20;
$items[4] = 20;
$items[5] = 20;
$item_count = count( $items );//物品总数
$box_volume_count = 100; //每个盒 子的最大容积
$box_count = 0; //共用盒子总数
$box = array();//盒子数组
for ( $itemindex = 0; $itemindex < $item_count; $itemindex++ ) {
$_box_index = false;
$_box_count = count( $box );
for ( $box_index = 0; $box_index < $_box_count; $box_index++ ) {
if ( $box[$box_index]['volume'] + $items[$itemindex] <= $box_volume_count ) {
$_box_index = $box_index;
break;
}
}
if ( $_box_index === false ) {
$box[$_box_count]['volume'] = $items[$itemindex];
$box[$_box_count]['items'][] = $itemindex;
$box_count++;
} else {
$box[$_box_index]['volume'] += $items[$itemindex];
$box[$_box_index]['items'][] = $itemindex;
}
}
print_r( $box );
结果:
Array
(
[0] => Array
(
[volume] => 95
[items] => Array
(
[0] => 0
[1] => 2
)
)
[1] => Array
(
[volume] => 85
[items] => Array
(
[0] => 1
[1] => 3
[2] => 4
)
)
[2] => Array
(
[volume] => 20
[items] => Array
(
[0] => 5
)
)
)