Implementácia problému batohu v Jave
1. Úvod
Problém s batohom je problém kombinatorickej optimalizácie, ktorý má veľa aplikácií. V tejto príručke tento problém vyriešime v prostredí Java.
2. Problém s batohom
V úlohe batohu máme sadu predmetov. Každá položka má váhu a hodnotu:
Tieto veci chceme vložiť do batohu. Má však hmotnostný limit:
Preto musíme vyberať položky, ktorých celková hmotnosť nepresahuje hmotnostný limit a ich celková hodnota je čo najvyššia. Najlepším riešením pre vyššie uvedený príklad je napríklad výber položky 5 kg a položky 6 kg, čo dáva maximálnu hodnotu 40 dolárov v rámci hmotnostného limitu.
Problém s batohom má niekoľko variácií. V tomto tutoriáli sa zameriame na problém s batohom 0-1. V probléme s batohom 0-1 musí byť každá položka buď vybraná, alebo zanechaná. Nemôžeme vziať čiastočné množstvo položky. Tiež nemôžeme vziať položku viackrát.
3. Matematická definícia
Poďme teraz formovať problém s batohom 0-1 matematickým zápisom. Vzhľadom na súbor n položky a hmotnostný limit Ž, môžeme optimalizačný problém definovať ako:
Tento problém je NP-ťažký. Preto v súčasnosti neexistuje žiadny algoritmus polynomiálneho času, ktorý by ho vyriešil. Existuje však pseudo-polynomiálny časový algoritmus využívajúci dynamické programovanie tohto problému.
4. Rekurzívne riešenie
Na vyriešenie tohto problému môžeme použiť rekurzný vzorec:
V tomto vzorci M (n, w) je optimálnym riešením pre n položky s hmotnostným limitom w. Je to maximum z nasledujúcich dvoch hodnôt:
- Optimálne riešenie od (n-1) položky s hmotnostným limitom w (okrem n-tá položka)
- Hodnota n-tá položka plus optimálne riešenie od (n-1) položky a w mínus hmotnosť n-. položka (vrátane n-tá položka)
Ak je váha n-stá položka je viac ako súčasný hmotnostný limit, nezahŕňame ju. Preto patrí do prvej kategórie vyššie uvedených dvoch prípadov.
Tento vzorec rekurzie môžeme implementovať v Jave:
int knapsackRec (int [] w, int [] v, int n, int W) {if (n W) {return knapsackRec (w, v, n - 1, W); } else {return Math.max (knapsackRec (w, v, n - 1, W), v [n - 1] + knapsackRec (w, v, n - 1, W - w [n - 1])); }} V každom kroku rekurzie musíme vyhodnotiť dve suboptimálne riešenia. Preto je prevádzková doba tohto rekurzívneho riešenia O (2n).
5. Dynamické programovacie riešenie
Dynamické programovanie je stratégia na linearizáciu inak exponenciálne zložitých problémov s programovaním. Cieľom je uložiť výsledky čiastkových problémov tak, aby sme ich neskôr nemuseli prepočítavať.
Problém s batohom 0-1 môžeme vyriešiť aj pomocou dynamického programovania. Aby sme mohli používať dynamické programovanie, najskôr si vytvoríme dvojrozmernú tabuľku s rozmermi od 0 do n a 0 až Ž. Potom použijeme prístup zdola nahor a pomocou tejto tabuľky vypočítame optimálne riešenie:
int knapsackDP (int [] w, int [] v, int n, int W) {if (n <= 0 || W <= 0) {return 0; } int [] [] m = nový int [n + 1] [W + 1]; pre (int j = 0; j <= W; j ++) {m [0] [j] = 0; } for (int i = 1; i <= n; i ++) {for (int j = 1; j j) {m [i] [j] = m [i - 1] [j]; } else {m [i] [j] = Math.max (m [i - 1] [j], m [i - 1] [j - w [i - 1]] + v [i - 1]); }}} návrat m [n] [W]; } V tomto riešení máme vnorenú slučku nad číslom položky n a hmotnostný limit Ž. Preto je čas spustenia taký, aký je O (nW).
6. Záver
V tomto tutoriáli sme si ukázali matematickú definíciu problému s batohom 0-1. Potom sme poskytli rekurzívne riešenie tohto problému s implementáciou Java. Nakoniec sme na riešenie tohto problému použili dynamické programovanie.
Zdrojový kód článku je ako vždy k dispozícii na stránkach GitHub.
