Како решити проблем фракционог ранца у Ц++

Дати скуп предмета, сваки са задатом тежином и профитом, одредите сваки број артикала у таквој комбинацији да укупна тежина предмета буде мања од максималне границе торбе, али вредност мора бити што већа.

Алгоритам за имплементацију проблема фракционог ранца

Функционисање Кнапсацк алгоритма се може разумети кроз следеће тачке:

Узмите два низа тежине и профита.
Поставите максималну вредност вреће на В.
Одредите густину узимајући однос оба параметра.
Сортирај ставке по опадајућем редоследу густине.
Додајте вредности док не буде <=В.

Похлепни приступ решавању проблема фракционог ранца

Похлепни приступ има за циљ да направи идеалне изборе на сваком кораку, доводећи до идеалног решења на крају. Решава проблеме корак по корак доводећи до закључака уместо да само на крају закључује резултате. Ово је изворни код за имплементацију решења за проблем фракционог ранца у Ц++:

#инцлуде <битс/стдц++.х>

Користећи именског простора стд ;

струцт Објекат {

инт вредност, тежина ;

Објекат ( инт вредност, инт тежина )
: вредност ( вредност ) , тежина ( тежина )
{
}

} ;

боол цмп ( струцт Објекат к, струцт Објекат и )

{

дупло А1 = ( дупло ) Икс. вредност / Икс. тежина ;

дупло А2 = ( дупло ) и. вредност / и. тежина ;

повратак А1 > А2 ;

}

дупло фрацтионалКнапсацк ( струцт Објекат арр [ ] ,
инт ИН, инт величина )
{

врста ( арр, арр + величина, цмп ) ;

инт цурВеигхт = 0 ;

дупло коначна вредност = 0.0 ;

за ( инт и = 0 ; и < величина ; и ++ ) {

ако ( цурВеигхт + арр [ и ] . тежина <= ИН ) {
цурВеигхт + = арр [ и ] . тежина ;
коначна вредност + = арр [ и ] . вредност ;
}

друго {
инт остати = ИН - цурВеигхт ;
коначна вредност + = арр [ и ] . вредност
* ( ( дупло ) остати
/ арр [ и ] . тежина ) ;

пауза ;
}
}

повратак коначна вредност ;

}

инт ин = 60 ;

Објецт арр [ ] = { { 100 , двадесет } ,
{ 380 , 40 } ,
{ 140 , 10 } ,
{ 180 , 30 } } ;

инт величина = величина ( арр ) / величина ( арр [ 0 ] ) ;

цоут << 'Максимални профит = '

<< фрацтионалКнапсацк ( арр, в, величина ) ;

повратак 0 ;

}

У овом коду је дефинисана структура објекта која има похрањене вредности тежине и профита. Боол цмп() се користи за поређење између два објекта на основу односа тежине и вредности два објекта. Низ је распоређен у опадајућем редоследу и вредност наставља да се додаје све док не достигне максимум. Ако је тренутна вредност дозвољена и унутар границе, она се додаје, у супротном се њен смањени однос додаје у врећу. Величина тежине и вредности се уносе у главни код, а максимални профит се штампа на излазу.

Максимални профит који је ускладиштен у ужини је 580.

Закључак

Проблем фракционог ранца у Ц++ односи се на идентификацију начина да се торба напуни предметима дате тежине и профита на такав начин да торба садржи максималну вредност без прекорачења максималног ограничења. Ово се може постићи похлепним приступом који има за циљ да направи идеалне изборе на сваком кораку, доводећи до идеалног решења на крају.

Како решити проблем фракционог ранца у Ц++