近似算法---首次適宜法
來源：程序員人生 發布時間：2016-07-05 14:49:53 閱讀次數：2436次
該算法實現非常簡單，思路大概是這模樣的:
定義若干個空箱子，假定箱子的體積有多大，然后把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
生活不易，碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈
