Zadanie - problem plecakowy

Question

Witam, mam zadanie z algorytmów i struktur danych, w którym mam rozwiązać decyzyjny problem plecakowy, treść jest podana na zdjęciu, za pomocą metody brutalnej siły. Mam rozwiązanie tego zadania ale nie rozumiem wcale jak to działa. Mógłby ktoś pomóc i wytłumaczyć mi to? Głównie chodzi mi o działanie tych pętli. 

 

package plecakowy;

/* 
 Rozwiazanie decyzyjnego problemu plecakowego
 Metoda brutalnej sily - iteracyjnie (za pomoca petli zagniezdzonych)
 */
public class PleacakBSIteracyjnie {

    final static int N = 6;                // liczba przedmiotów
    final static int MAX_V = 10;           // objetość plecaka

    final static int[] V = {2, 6, 3, 3, 1, 2};  // objetości przedmiotów
    final static int[] W = {4, 6, 5, 10, 2, 7}; // wartości przedmiotów

    public static void main(String[] args) {
        int maxW = 0;
        int v, w;
        int b1, b2, b3, b4, b5, b6;
        int[] tab = new int[N]; // tablica na info o przedmiotach w plecaku
        for (b1 = 0; b1 <= 1; b1++) {
            for (b2 = 0; b2 <= 1; b2++) {
                for (b3 = 0; b3 <= 1; b3++) {
                    for (b4 = 0; b4 <= 1; b4++) {
                        for (b5 = 0; b5 <= 1; b5++) {
                            for (b6 = 0; b6 <= 1; b6++) {
                                v = b1 * V[0] + b2 * V[1] + b3 * V[2]
                                        + b4 * V[3] + b5 * V[4] + b6 * V[5];
                                if (v <= MAX_V) {
                                    w = b1 * W[0] + b2 * W[1] + b3 * W[2]
                                            + b4 * W[3] + b5 * W[4] + b6 * W[5];
                                    if (w > maxW) {
                                        maxW = w;
                                        tab[0] = b1;
                                        tab[1] = b2;
                                        tab[2] = b3;
                                        tab[3] = b4;
                                        tab[4] = b5;
                                        tab[5] = b6;
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }

        System.out.println("Wartosc przedmiotów w plecaku, to:  " + maxW);
        System.out.print("W plecaku są przedmioty o numerach :  ");
        for (int i = 0; i < N; i++) {
            if (tab[i] == 1) {
                System.out.print(i + " ");
            }
        }

        System.out.println();
    }
}

 

Answer 1

W Algorytmie Plecakowym, wykorzystując "brutalną siłę" chodzi o to, że po prostu sprawdzasz każdą możliwą kombinację par waga-wartość.

Ta zmienna w (z tym takim długim wzorem),  to suma wag dla każdego wariantu (1*cokolwiek = cokolwiek, 0* cokolwiek=0). Wszystkie te pętle to masz po prostu "odzwierciedlenie" czy w danej kombinacji jest przedmiot (zmienna sterująca pętla =1) lub go nie ma (0) Jeżeli kombinacja będzie możliwa, tzn waga będzie mniejsza bądź równa udzwigowi, wtedy dodajesz wartości dla "tego wariantu". Jeżeli będzie większa od Max, to przypisujesz max tą wartość. I "przedmioty" (a raczej ich wartości) przechowujesz w tablicy.

Answer 2

Dzielisz Wi / Vi i wychodzi ci wartość przedmiotu na jednostkę objętości a później ładujesz do plecaka w pierwszej kolejności te, które mają największą wyliczoną wartość.

Comments

Nie rozumiem, gdzie tam jest dzielenie jakieś? Bo ja nie widzę.

---

W przykładzie z brutalną siłą nie ma, ale mógłbyś to tak zaimplementowac żeby było optymalniej i łatwiej dodawać kolejne elementy.

-------

Btw: co jeśli byś miał parę takich liczb z największym stosunkiem V/waga? Reszta mało rozniaca się.

Edit: albo najprostszy przykład: Plecak może przechować przedmioty o wadze 10. A możesz tam wlzyc przedmioty takie jak:

- waga 2 - wartość 7

- waga 10 - wartość 8.

Co byś włożył? Bo lżejszy przedmiot ma znacznie wyższy stosunek od ciezszego.

---

W treści zadania nie zauważyłem ani słowa o tym, że to ma być zrobione metodą brutal-force.

---

Co nie zmienia faktu, że istnieje lepszy algorytm i bardziej dokładny niż wyszukiwanie elementów o największym współczynniku wartość/masa