Introduksjon
Brøksekkproblemet er et velkjent optimaliseringsproblem innen informatikk. Det oppstår når vi har et sett med gjenstander, hver med sin vekt og verdi, og en sekk med begrenset kapasitet. Målet er å fylle sekken med de mest verdifulle gjenstandene uten å overskride kapasiteten.
I motsetning til 0-1-sekkproblemet, hvor vi kun kan inkludere en gjenstand i sekken én gang, kan vi i brøksekkproblemet inkludere en brøkdel av en gjenstand. Dette gjør problemet mer utfordrende og krever en annen tilnærming for å løse det.
Algoritme
Den grådige algoritmen for å løse brøksekkproblemet er som følger:
- Sorter gjenstandene i synkende rekkefølge etter deres forhold mellom verdi og vekt.
- Begynn å fylle sekken med gjenstandene i denne rekkefølgen.
- Dersom den nåværende gjenstanden overskrider den gjenværende kapasiteten til sekken, inkluder en brøkdel av gjenstanden som akkurat fyller sekken.
- Gjenta trinn 2 og 3 til sekken er full.
C++ Implementasjon
Følgende C++-kode implementerer den grådige algoritmen for brøksekkproblemet:
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct Item {
int weight;
int value;
double value_per_weight;
};
bool compareItems(const Item& a, const Item& b) {
return a.value_per_weight > b.value_per_weight;
}
int main() {
int capacity;
int num_items;
cout << "Skriv inn sekkens kapasitet: ";
cin >> capacity;
cout << "Skriv inn antall gjenstander: ";
cin >> num_items;
vector<Item> items(num_items);
for (int i = 0; i < num_items; i++) {
cout << "Skriv inn vekten til gjenstand " << i + 1 << ": ";
cin >> items[i].weight;
cout << "Skriv inn verdien til gjenstand " << i + 1 << ": ";
cin >> items[i].value;
items[i].value_per_weight = (double)items[i].value / items[i].weight;
}
sort(items.begin(), items.end(), compareItems);
double total_value = 0;
int remaining_capacity = capacity;
for (int i = 0; i < num_items; i++) {
if (remaining_capacity >= items[i].weight) {
total_value += items[i].value;
remaining_capacity -= items[i].weight;
} else {
double fraction = (double)remaining_capacity / items[i].weight;
total_value += fraction * items[i].value;
remaining_capacity = 0;
break;
}
}
cout << "Maksimal verdi: " << total_value << endl;
return 0;
}
Eksempel
La oss si vi har følgende gjenstander:
| Gjenstand | Vekt | Verdi |
| A | 1 | 5 |
| B | 3 | 10 |
| C | 4 | 12 |
| D | 2 | 8 |
Og en sekk med en kapasitet på 5.
Løsning:
- Sorter gjenstandene i synkende rekkefølge etter forholdet mellom verdi og vekt:
| Gjenstand | Vekt | Verdi | Forhold verdi-vekt |
| C | 4 | 12 | 3 |
| B | 3 | 10 | 3.33 |
| D | 2 | 8 | 4 |
| A | 1 | 5 | 5 |
- Begynn å fylle sekken med gjenstandene i denne rekkefølgen:
– Legg til gjenstand C i sekken (vekt = 4, verdi = 12).
– Legg til gjenstand B i sekken (vekt = 3, verdi = 10).
- Gjenstand D overskrider gjenværende kapasitet (5 – 4 – 3 = -2). Derfor inkluderer vi en brøkdel av gjenstand D som akkurat fyller sekken:
– Brøk = gjenværende_kapasitet / vekt_av_gjenstand_D = 2 / 2 = 1
– Verdi = brøk * verdi_av_gjenstand_D = 1 * 8 = 8
- Total verdi = verdi_av_gjenstand_C + verdi_av_gjenstand_B + verdi_av_brøkdel_av_gjenstand_D = 12 + 10 + 8 = 30
Konklusjon
Brøksekkproblemet er et utfordrende optimaliseringsproblem som har mange anvendelser i praktiske scenarier, som ressursallokering, porteføljeoptimalisering og planlegging. Den grådige algoritmen som er presentert i denne artikkelen, gir en enkel og effektiv måte å løse problemet på og maksimere den totale verdien som oppnås.
Ofte stilte spørsmål (FAQ)
- Hva er forskjellen mellom 0-1-sekkproblemet og brøksekkproblemet?
– I 0-1-sekkproblemet kan du kun inkludere en gjenstand i sekken én gang. I brøksekkproblemet kan du inkludere en brøkdel av en gjenstand. - Hva er tidskompleksiteten til den grådige algoritmen for brøksekkproblemet?
– Tidskompleksiteten er O(n log n), der n er antall gjenstander. - Når brukes brøksekkproblemet i praktiske anvendelser?
– Brøksekkproblemet brukes i ulike scenarioer, inkludert ressursallokering, porteføljeoptimalisering og planlegging. - Kan den grådige algoritmen alltid finne den optimale løsningen for brøksekkproblemet?
– Ja, den grådige algoritmen finner alltid den optimale løsningen for brøksekkproblemet. - Hvordan kan jeg forbedre effektiviteten til den grådige algoritmen?
– Du kan bruke ulike teknikker for å forbedre effektiviteten til den grådige algoritmen, som for eksempel å bruke en min-heap eller et binært søketre. - Hvilke anvendelser har brøksekkproblemet i ulike bransjer?
– Brøksekkproblemet brukes i bransjer som informatikk, økonomi og ingeniørfag. - Hvordan kan jeg lære mer om brøksekkproblemet?
– Du kan referere til bøker, artikler og ressurser på nettet for å lære mer om brøksekkproblemet. - Hva er utfordringene og begrensningene ved brøksekkproblemet?
– Utfordringene og begrensningene ved brøksekkproblemet inkluderer dets tidskompleksitet og dets antagelser om linearitet og delelighet.