Zaino frazionario utilizzando C++

Zaino frazionario utilizzando C++

Lo zaino frazionario è una variante dello zaino 0-1 in cui gli oggetti possono essere suddivisi in frazioni arbitrarie. Si tratta di un problema di ottimizzazione combinatoria che trova applicazione in vari ambiti, tra cui la gestione delle risorse, la pianificazione della produzione e la logistica.

In questo articolo, esploreremo il problema dello zaino frazionario e forniremo un’implementazione in C++. Discuteremo gli aspetti teorici e pratici dell’algoritmo e forniremo esempi per illustrare il suo funzionamento.

Algoritmo avido per lo zaino frazionario

L’algoritmo avido per lo zaino frazionario si basa sull’idea di selezionare gli oggetti con la massima efficienza, ovvero il rapporto tra il valore e il peso. L’algoritmo funziona come segue:

1. Ordina gli oggetti in ordine decrescente di efficienza.
2. Inizia ad aggiungere oggetti allo zaino, a partire dall’oggetto più efficiente.
3. Se l’aggiunta di un oggetto supera la capacità dello zaino, aggiungi una frazione dell’oggetto sufficiente a riempire lo zaino.
4. Continua ad aggiungere oggetti finché lo zaino non è pieno.

Implementazione in C++

Di seguito è riportata un’implementazione dell’algoritmo avido per lo zaino frazionario in C++:

cpp
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// Oggetto zaino
struct Item {
int value;
int weight;
double efficiency;
};

// Comparatore per l'efficienza
bool compareEfficiency(const Item& a, const Item& b) {
return a.efficiency > b.efficiency;
}

// Funzione zaino frazionario
int fractionalKnapsack(vector<Item>& items, int capacity) {
// Ordina gli oggetti in ordine decrescente di efficienza
sort(items.begin(), items.end(), compareEfficiency);

// Inizializza il valore totale
int totalValue = 0;

// Iterare sugli oggetti
for (const Item& item : items) {
// Se lo zaino è pieno, esci
if (capacity <= 0) {
break;
}

// Ottieni la frazione dell'oggetto da aggiungere allo zaino
double fraction = min((double)capacity / item.weight, 1.0);

// Aggiungi la frazione dell'oggetto allo zaino
totalValue += fraction * item.value;

// Aggiorna la capacità dello zaino
capacity -= fraction * item.weight;
}

return totalValue;
}

int main() {
// Oggetti
vector<Item> items = {
{10, 2},
{5, 3},
{15, 5},
{7, 7},
{6, 1}
};

// Capacità dello zaino
int capacity = 15;

// Calcola il valore totale
int totalValue = fractionalKnapsack(items, capacity);

// Stampa il valore totale
cout << "Valore totale: " << totalValue << endl;

return 0;
}


Esempio

Consideriamo un insieme di oggetti con i seguenti valori e pesi:

| Oggetto | Valore | Peso |
|—|—|—|
| Oggetto 1 | 10 | 2 |
| Oggetto 2 | 5 | 3 |
| Oggetto 3 | 15 | 5 |
| Oggetto 4 | 7 | 7 |
| Oggetto 5 | 6 | 1 |

Supponiamo di avere uno zaino con una capacità di 15. Applicando l’algoritmo avido dello zaino frazionario, otterremo la seguente soluzione:

* Aggiungi l’oggetto 5 allo zaino (valore: 6, peso: 1)
* Aggiungi una frazione dell’oggetto 1 allo zaino (valore: 8, peso: 2)
* Aggiungi una frazione dell’oggetto 3 allo zaino (valore: 6, peso: 2)
* Lo zaino è ora pieno con un valore totale di 20

Conclusioni

Lo zaino frazionario è un problema di ottimizzazione combinatoria che trova applicazione in una vasta gamma di settori. L’algoritmo avido fornisce una soluzione semplice ed efficiente che può essere implementata in C++. Capire come funziona questo algoritmo è essenziale per risolvere problemi reali di allocazione e gestione delle risorse.

Domande frequenti

1. Qual è la differenza tra zaino 0-1 e zaino frazionario?
> Lo zaino 0-1 consente di selezionare solo interi oggetti, mentre lo zaino frazionario consente di suddividere gli oggetti in frazioni.

2. L’algoritmo avido dello zaino frazionario è sempre ottimale?
> No, non è sempre ottimale, ma fornisce una buona soluzione approssimativa nella maggior parte dei casi.

3. Quali sono le applicazioni del problema dello zaino frazionario?
> Gestione delle risorse, pianificazione della produzione, logistica, selezione del portafoglio e molti altri.

4. Quali sono i vantaggi dell’implementazione in C++?
> Efficienza, controllo di basso livello e utilizzo diffuso in software di produzione.

5. Posso modificare l’algoritmo per gestire vincoli aggiuntivi?
> Sì, è possibile modificare l’algoritmo per gestire vincoli come il numero massimo di oggetti o vincoli di precedenza.

6. Come posso migliorare la performance dell’algoritmo?
> Utilizzando tecniche come la programmazione dinamica o la branch and bound.

7. Quali sono le alternative all’algoritmo avido?
> Algoritmi esatti come la programmazione intera mista o algoritmi approssimativi come l’algoritmo di approssimazione di bin-packing.

8. Dove posso trovare ulteriori risorse sull’argomento?
> GeeksforGeeks, Coursera, TutorialsPoint