Study of Branch & Bound
A New Approach to 0/1 Knapsack Problem with Greedy and Heuristic Searches in Integer Programming
Tam Sayı Programlamada Açgözlü ve Sezgisel Aramalar ile 0/1 Sırt Çantası Problemine Yeni Bir Bakış
The web link of the article is here
Download the article in PDF format.
Abstract:
Integer programming is a type of optimized Linear Programming method. The goal is to get rid of unrealistic results that might occur in the linear programming process. Integer Programming is applied to many engineering fields. In this study, a new heuristic and greedy approach to the conventional Integer Programming method is proposed to the well-known knapsack problem, which is accepted as the source of many engineering problems. Heap data structure, additionally, is used in order to decrease both space complexity and implementation time. In the experimental applications, it is observed that the proposed method yields less computational time than the recursive, pruned, and optimized methods.
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
