Study of  Branch & Bound

A-Star Heuristic Approach ile Branch&Bound Algorithm can be applied to the KnapSack problem. The problem and the implemented C/C++ codes can be as follows: 

Branch & Bound

Yangından Mal Kaçırma

Aynı okulda öğrenci olan Mustafa ile Mehmet, Yunus ve İshak ikilisinden pek hoşlanmadıkları için yurtta sürekli bir yerleri yakmaktadırlar. Yunus ve İshak ikilisi bilgisayar olimpiyatçısı olduğu için yurt müdürü Bahadır bey, bu ikiliyi yurdun itfaiye birliğine seçmiştir. Bahadır Bey’in isteği yurttaki demirbaşların en önemlilerin kurtarılmasıdır. Bunun için Bahadır Bey Yunus ve İshak’a demirbaş listesini vermiştir. Yunus bu sorunu Knapsack algoritmasını kullanarak çözerken İshak başka bir algoritma kullanmak istemiştir. Aklına ilk olarak Branch & Bound algoritması gelmiştir. Sizden istenen bu sorunu tıpkı İshak gibi Branch & Bound algoritmasıyla çözmenizdir.

Girdi :

girdi.in dosyasının ilk satırda demirbaş sayısı N, çantanın kapasite değeri K verilmektedir.

Sonraki N satırda ise her demirbaşın ağırlığı ve pahası verilmektedir.

Çıktı :

cikti.out dosyasında kurtarılan demirbaşların değerleri toplamı.

Örnek Girdi ve Çıktı :

girdi.in

4 16

4 12

7 63

8 56

10 100

cikti.out

119

Kısıtlar :

N < 30

K < 100.000

Ağırlık ve Paha < 10.000

Hesaplama Süresi < 1sn

C/C++ Çözüm Kodları şu şekilde:

#include<stdio.h>

FILE *oku,*yaz;

int dizi[3000][3];

int parca_sayisi,kapasite;

int upperbound;

int alt_sinir=0;

int cmp(int *a,int *b)

{

      return *(a+2)<*(b+2);

}

void Oku()

{

      int i;

      oku=fopen("girdi.in","r");

      fscanf(oku,"%d %d ",&parca_sayisi,&kapasite);

      for(i=0;i<parca_sayisi;i++)

      {

            fscanf(oku,"%d %d ",&dizi[i][0],&dizi[i][1]);

            dizi[i][2]=dizi[i][1]/dizi[i][0];//dizi[i][2]=birim agirligi

      }

      qsort(dizi,parca_sayisi,sizeof(int)*3,cmp);//birim degerine gore buyukten kucuge siraladik

      upperbound=dizi[0][2]*kapasite;//ustsinir'i buluyoruz //en buyuk birim degerlinin birim degeriyle kapasiteyi carptik

}

void Rec(int kullanilan_kapasite,int esya,int deger)

{

      if(esya==parca_sayisi)//butun esyalari denemissek

            {

                  if(deger>alt_sinir)//daha buyuk sonuc bulmussak

                        alt_sinir=deger;

                  return;

            }

      if(deger+dizi[esya][2]*(kapasite-kullanilan_kapasite)<alt_sinir)//alt sinirdan kucukse return et

            return;

      if(kullanilan_kapasite+dizi[esya][0]<=kapasite && deger+dizi[esya][1]<upperbound)//esyayi larak gitme

            Rec(kullanilan_kapasite+dizi[esya][0],esya+1,deger+dizi[esya][1]);

      Rec(kullanilan_kapasite,esya+1,deger);//esyayi almadan gitme

}

void Yaz()

{

      yaz=fopen("cikti.out","w");

      fprintf(yaz,"%d\n",alt_sinir);      //Alt sinir yani cantayi kapasiteyi asmadan doldurabilecegimiz en degerli durum

      fclose(yaz);     

}

int main()

{

      Oku();      //Okuma islemlerini yapiyoruz

      Rec(0,0,0); //upperboundu gecmeyen ve sonuc olarak buldugumuz en buyuk degerden kucuk olmayan tum durumlari deneyecek Recursive fonksiyon

      Yaz();      // Ve son olarak yazma islemi

      return 0;

}

C/C++ kodları için test girdi ve çıktıları için burayı tıklayın.

Referans vermek için (for citations):

Faruk BULUT, İ. Furkan INCE, "Tam Sayı Programlamada Açgözlü ve Sezgisel Aramalar ile 0/1 Sırt Çantası Problemine Yeni Bir Bakış", 2018