Il problema dello zaino frazionario in C++ si riferisce all'identificazione di un modo per riempire una borsa con oggetti di un determinato peso e profitto in modo tale che la borsa contenga il valore massimo senza superare il limite massimo.
Come risolvere il problema dello zaino frazionario in C++
Dato un insieme di articoli, ciascuno con il peso e il profitto indicati, determina ciascun numero di articoli in una combinazione tale che il peso totale degli articoli sia inferiore al limite massimo del sacchetto, ma il valore deve essere mantenuto il più grande possibile.
Algoritmo per implementare il problema dello zaino frazionario
Il funzionamento dell’algoritmo Knapsack può essere compreso attraverso i seguenti punti:
- Prendi due matrici di peso e profitto.
- Impostare il valore massimo del sacco su W.
- Determina la densità prendendo il rapporto tra entrambi i parametri.
- Ordina gli elementi in ordine decrescente di densità.
- Somma i valori finché non è <=W.
L'approccio avido per risolvere il problema dello zaino frazionario
L’approccio avido mira a fare scelte ideali in ogni fase, portando alla fine alla soluzione ideale. Risolve i problemi passo dopo passo portando a conclusioni invece di concludere i risultati solo alla fine. Questo è un codice sorgente per implementare una soluzione al problema dello zaino frazionario in C++:
#include
utilizzando spazio dei nomi standard ;
struttura Oggetto {
int valore, peso ;
Oggetto ( int valore, int peso )
: valore ( valore ) , peso ( peso )
{
}
} ;
bool cmp ( struttura Oggetto x, struttura Oggetto y )
{
Doppio A1 = ( Doppio ) X. valore / X. peso ;
Doppio A2 = ( Doppio ) E. valore / E. peso ;
ritorno A1 > A2 ;
}
Doppio zaino frazionario ( struttura Oggetto arr [ ] ,
int IN, int misurare )
{
ordinare ( arr, arr + dimensione, cm ) ;
int curWeight = 0 ;
Doppio valorefinale = 0,0 ;
per ( int io = 0 ; io < misurare ; io ++ ) {
Se ( curWeight + arr [ io ] . peso <= IN ) {
curWeight + = arr [ io ] . peso ;
valorefinale + = arr [ io ] . valore ;
}
altro {
int rimanere = IN - curWeight ;
valorefinale + = arr [ io ] . valore
* ( ( Doppio ) rimanere
/ arr [ io ] . peso ) ;
rottura ;
}
}
ritorno valorefinale ;
}
int In = 60 ;
Oggetto arr [ ] = { { 100 , venti } ,
{ 380 , 40 } ,
{ 140 , 10 } ,
{ 180 , 30 } } ;
int misurare = taglia di ( arr ) / taglia di ( arr [ 0 ] ) ;
cout << 'Profitto massimo = '
<< zaino frazionario ( arr, v, dimensione ) ;
ritorno 0 ;
}
In questo codice viene definita una struttura di oggetto in cui sono memorizzati valori di peso e profitto. Il metodo bool cmp() viene utilizzato per effettuare un confronto tra due oggetti sulla base del rapporto tra peso e valore di due oggetti. L'array è organizzato in ordine decrescente e il valore continua ad aggiungersi fino a raggiungere il massimo. Se il valore corrente è ammissibile ed entro il limite, viene aggiunto, altrimenti viene aggiunto al sacco il suo rapporto ridotto. L'entità del peso e del valore viene immessa nel codice principale e il profitto massimo viene stampato sull'output.
Il profitto massimo immagazzinato nello snack è 580.
Conclusione
Il problema dello zaino frazionario in C++ si riferisce all'identificazione di un modo per riempire una borsa con oggetti di un determinato peso e profitto in modo tale che la borsa contenga il valore massimo senza superare il limite massimo. Ciò può essere ottenuto con un approccio avido che mira a fare scelte ideali in ogni fase, portando alla fine alla soluzione ideale.