Jak vyřešit problém frakčního batohu v C++

Pro daný soubor položek, každý s danou hmotností a ziskem, určete každý počet položek v takové kombinaci, aby celková hmotnost položek byla menší než maximální limit pytle, ale hodnota musí být co největší.

Algoritmus k implementaci problému frakčního batohu

Fungování algoritmu batohu lze pochopit pomocí následujících bodů:

Vezměte dvě pole hmotnosti a zisku.
Nastavte maximální hodnotu pytle na W.
Hustotu určete poměrem obou parametrů.
Seřaďte položky v sestupném pořadí podle hustoty.
Sečtěte hodnoty, dokud nebude <=W.

Chamtivý přístup k vyřešení problému s částečným batohem

Chamtivý přístup si klade za cíl činit ideální volby v každém kroku, což na konci vede k ideálnímu řešení. Řeší problémy krok za krokem vedoucí k závěrům místo toho, aby nakonec došel až k výsledkům. Toto je zdrojový kód pro implementaci řešení problému frakčního batohu v C++:

#include

použitím jmenný prostor std ;

strukturovat Objekt {

int hodnota, hmotnost ;

Objekt ( int hodnota, int hmotnost )
: hodnota ( hodnota ) , hmotnost ( hmotnost )
{
}

} ;

bool cmp ( strukturovat objekt x, strukturovat Objekt y )

{

dvojnásobek A1 = ( dvojnásobek ) X. hodnota / X. hmotnost ;

dvojnásobek A2 = ( dvojnásobek ) a. hodnota / a. hmotnost ;

vrátit se A1 > A2 ;

}

dvojnásobek frakční batoh ( strukturovat Objekt arr [ ] ,
int V, int velikost )
{

seřadit ( arr, arr + velikost, cmp ) ;

int curWeight = 0 ;

dvojnásobek konečná hodnota = 0,0 ;

pro ( int i = 0 ; i < velikost ; i ++ ) {

-li ( curWeight + arr [ i ] . hmotnost <= V ) {
curWeight + = arr [ i ] . hmotnost ;
konečná hodnota + = arr [ i ] . hodnota ;
}

jiný {
int zůstat = V - curWeight ;
konečná hodnota + = arr [ i ] . hodnota
* ( ( dvojnásobek ) zůstat
/ arr [ i ] . hmotnost ) ;

přestávka ;
}
}

vrátit se konečná hodnota ;

}

int v = 60 ;

Objekt arr [ ] = { { 100 , dvacet } ,
{ 380 , 40 } ,
{ 140 , 10 } ,
{ 180 , 30 } } ;

int velikost = velikost ( arr ) / velikost ( arr [ 0 ] ) ;

cout << 'Maximální zisk ='

<< frakční batoh ( arr, v, velikost ) ;

vrátit se 0 ;

}

V tomto kódu je definována struktura objektu, která má v sobě uložené hodnoty váhy a zisku. Bool cmp() se používá k porovnání dvou objektů na základě poměru váhy a hodnoty dvou objektů. Pole je uspořádáno v sestupném pořadí a hodnota se neustále sčítá, dokud nedosáhne maxima. Je-li aktuální hodnota přípustná a v mezích, přičte se, v opačném případě se do sáčku přičte její redukovaný poměr. Velikost hmotnosti a hodnoty je zadána v hlavním kódu a maximální zisk je vytištěn na výstupu.

Maximální zisk, který byl uložen ve svačině, je 580.

Závěr

Problém frakčního batohu v C++ se týká identifikace způsobu, jak naplnit pytel položkami dané hmotnosti a zisku tak, aby pytel obsahoval maximální hodnotu, aniž by byl překročen maximální limit. Toho lze dosáhnout chamtivým přístupem, který si klade za cíl dělat v každém kroku ideální volby, které na konci vedou k ideálnímu řešení.

Jak vyřešit problém frakčního batohu v C++