C Knapsack Problems

Posted: October 9, 2014 in Algorithms, C
Tags: , ,

Dinamik programlama uygulamasına örnek olarak Knapsack(Sırt çantası) problemi.Problem, çeşitli değer ve hacimdeki nesnelerin sınırlı hacimli bir çantaya ,toplam değer maksimum olacak şekilde doldurulmasına dayanmaktadır.

Tablodaki gibi veriler elimizde olsun .

16

Örneğimizde maksimum hacim 7 olmalıymış.Kendimiz veri sayısı az olduğu için kaba-kuvvet yada deneme yöntemiyle bulabiliriz.Ama veri sayısı çok olduğu zaman bu doğru sonuç vermeyebilir.Aşağıdaki algoritma bu sebepten bulunmuştur.
Aşağıdaki program, C programlama dili ile yazılmıştır.

#include
#include

#define max(a,b) (a > b ? a : b)

int matrix[100][100] = {0};

int knapsack(int index, int size, int hacim[],int deger[]){
int take,dontTake;

take = dontTake = 0;

if (matrix[index][size]!=0)
return matrix[index][size];

if (index==0){
if (hacim[0]<=size){
matrix[index][size] = deger[0];
return deger[0];
}
else{
matrix[index][size] = 0;
return 0;
}
}

if (hacim[index]<=size)
take = deger[index] + knapsack(index-1, size-hacim[index], hacim, deger);

dontTake = knapsack(index-1, size, hacim, deger);

matrix[index][size] = max (take, dontTake);

return matrix[index][size];

}

int main(){
int nItems = 4;
int knapsackSize = 7;
int hacim[4] = {2,3,1,4};
int deger[4] = {3,5,2,4};

printf(“Max value = %d tl”,knapsack(nItems-1,knapsackSize,hacim,deger));

return 0;
}

17

Programın çıktısı :

18

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s