• Najnowsze pytania
  • Bez odpowiedzi
  • Zadaj pytanie
  • Kategorie
  • Tagi
  • Zdobyte punkty
  • Ekipa ninja
  • IRC
  • FAQ
  • Regulamin
  • Książki warte uwagi

Zadanie - problem plecakowy

0 głosów
562 wizyt
pytanie zadane 14 listopada 2017 w Java przez barteku12 Obywatel (1,060 p.)

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();
    }
}

 

2 odpowiedzi

+1 głos
odpowiedź 14 listopada 2017 przez Aisekai Nałogowiec (25,670 p.)
wybrane 14 listopada 2017 przez barteku12
 
Najlepsza
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.
+1 głos
odpowiedź 14 listopada 2017 przez obl Nałogowiec (43,100 p.)
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ść.
komentarz 14 listopada 2017 przez barteku12 Obywatel (1,060 p.)
Nie rozumiem, gdzie tam jest dzielenie jakieś? Bo ja nie widzę.
komentarz 14 listopada 2017 przez Aisekai Nałogowiec (25,670 p.)
edycja 14 listopada 2017 przez Aisekai
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.
komentarz 14 listopada 2017 przez obl Nałogowiec (43,100 p.)
W treści zadania nie zauważyłem ani słowa o tym, że to ma być zrobione metodą brutal-force.
komentarz 14 listopada 2017 przez Aisekai Nałogowiec (25,670 p.)
Co nie zmienia faktu, że istnieje lepszy algorytm i bardziej dokładny niż wyszukiwanie elementów o największym współczynniku wartość/masa

Podobne pytania

0 głosów
1 odpowiedź 78 wizyt
pytanie zadane 28 grudnia 2016 w C# i .NET przez Kobis Nowicjusz (120 p.)
0 głosów
2 odpowiedzi 291 wizyt
pytanie zadane 6 maja 2017 w C i C++ przez Barteck125 Obywatel (1,140 p.)
0 głosów
1 odpowiedź 131 wizyt
Porady nie od parady
Odznacz odpowiedź zieloną fajką, jeśli uważasz, że jest ona najlepsza ze wszystkich i umożliwiła ci rozwiązanie problemu.Najlepsza odpowiedź

52,093 zapytań

94,979 odpowiedzi

193,662 komentarzy

25,394 pasjonatów

Przeglądających: 208
Pasjonatów: 14 Gości: 194

Motyw:

Akcja Pajacyk

Pajacyk od wielu lat dożywia dzieci. Pomóż klikając w zielony brzuszek na stronie. Dziękujemy! ♡

Oto dwie polecane książki warte uwagi. Pełną listę znajdziesz tutaj.

...