C++'daki kesirli sırt çantası problemi, bir torbayı belirli bir ağırlığa ve kâra sahip öğelerle, torbanın maksimum sınırı aşmadan maksimum değeri içerecek şekilde doldurmanın bir yolunun belirlenmesini ifade eder.
C++'da Kesirli Sırt Çantası Problemi Nasıl Çözülür?
Her biri verilen ağırlığa ve kâra sahip bir dizi öğe verildiğinde, öğelerin toplam ağırlığı torbanın maksimum sınırından az olacak, ancak değerin mümkün olduğu kadar büyük tutulması gereken bir kombinasyondaki her öğe sayısını belirleyin.
Kesirli Sırt Çantası Problemini Uygulama Algoritması
Sırt Çantası algoritmasının işleyişi aşağıdaki noktalar aracılığıyla anlaşılabilir:
- Ağırlık ve kârın iki dizisini alın.
- Maksimum çuval değerini W olarak ayarlayın.
- Her iki parametrenin oranını alarak yoğunluğu belirleyin.
- Öğeleri azalan yoğunluk sırasına göre sıralayın.
- <=W olana kadar değerleri toplayın.
Kesirli Sırt Çantası Problemini Çözmek İçin Açgözlü Yaklaşım
Açgözlü yaklaşım, her adımda ideal seçimler yapmayı ve sonunda ideal çözüme ulaşmayı amaçlar. Yalnızca sonuçlara varmak yerine, sorunları adım adım çözerek sonuçlara varır. Bu, C++'daki kesirli sırt çantası sorununa bir çözüm uygulamaya yönelik bir kaynak kodudur:
#include
kullanarak ad alanı std ;
yapı Nesne {
int değer, ağırlık ;
Nesne ( int değer, int ağırlık )
: değer ( değer ) , ağırlık ( ağırlık )
{
}
} ;
bool cmp ( yapı nesne x, yapı nesne y )
{
çift A1 = ( çift ) X. değer / X. ağırlık ;
çift A2 = ( çift ) Ve. değer / Ve. ağırlık ;
geri dönmek A1 > A2 ;
}
çift fraksiyonelSırt Çantası ( yapı Nesne dizisi [ ] ,
int İÇİNDE, int boyut )
{
düzenlemek ( varış, varış + boyut, cmp ) ;
int CurWeight = 0 ;
çift nihai değer = 0,0 ;
için ( int Ben = 0 ; Ben < boyut ; Ben ++ ) {
eğer ( CurWeight + varış [ Ben ] . ağırlık <= İÇİNDE ) {
CurWeight + = varış [ Ben ] . ağırlık ;
nihai değer + = varış [ Ben ] . değer ;
}
başka {
int geriye kalmak = İÇİNDE - CurWeight ;
nihai değer + = varış [ Ben ] . değer
* ( ( çift ) geriye kalmak
/ varış [ Ben ] . ağırlık ) ;
kırmak ;
}
}
geri dönmek nihai değer ;
}
int içinde = 60 ;
Nesne dizisi [ ] = { { 100 , yirmi } ,
{ 380 , 40 } ,
{ 140 , 10 } ,
{ 180 , 30 } } ;
int boyut = boyutu ( varış ) / boyutu ( varış [ 0 ] ) ;
cout << 'Maksimum kar = '
<< fraksiyonelSırt Çantası ( arr, v, boyut ) ;
geri dönmek 0 ;
}
Bu kodda ağırlık ve kar değerlerinin saklandığı bir nesne yapısı tanımlanır. bool cmp() işlevi, iki nesnenin ağırlık ve değer oranına dayalı olarak iki nesne arasında karşılaştırma yapmak için kullanılır. Dizi azalan sırada düzenlenir ve değer maksimuma ulaşana kadar eklenmeye devam eder. Mevcut değer izin verilen ve limit dahilinde ise eklenir, aksi takdirde azaltılmış oranı torbaya eklenir. Ağırlık ve değerin büyüklüğü ana koda girilir ve maksimum kar çıktıya yazdırılır.
Atıştırmalıkta saklanan maksimum kar 580'dir.
Çözüm
C++'daki kesirli sırt çantası problemi, bir torbayı belirli bir ağırlığa ve kâra sahip öğelerle, torbanın maksimum sınırı aşmadan maksimum değeri içerecek şekilde doldurmanın bir yolunun belirlenmesini ifade eder. Bu da her adımda ideal seçimler yapmayı ve sonunda ideal çözüme ulaşmayı amaçlayan açgözlü yaklaşımla sağlanabilir.