近似算法---首次适宜法
来源:程序员人生 发布时间:2016-07-05 14:49:53 阅读次数:2234次
该算法实现非常简单,思路大概是这模样的:
定义若干个空箱子,假定箱子的体积有多大,然后把1些货物存在这些箱子里,当第1个箱子存满后,接着寄存第2个箱子,直到货物存完为止,我们来看看这个程序:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int FirstFit(int n , int C, int *s , int *b)
{
int i , j = 0 , k ;
k = 0;
memset(b,0,sizeof(b)/sizeof(b[0]));
for (i = 0; i< n; i ++ ) // 装入第 i 个物品
{
while ((C - b[j])< s[i]) // 查找第 1 个能容纳物品 i的箱子
j ++ ;
b[j] = b[j] + s[i] ;
if(j > k)k = j ;
else k = k ;
}
return k;
}
int main(void)
{
int i,j;
int b[10] = {0};
int s[10] = {10 , 20 , 30 , 40 , 50 , 60 , 70 , 80 , 90 , 100} ;
FirstFit(10,100,s,b);
for(i = 0 ; i < 10 ; i++)
{
printf("%d\n",b[i]);
}
return 0 ;
}
运行结果:
100
50
60
70
80
90
100
0
0
0
生活不易,码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠