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

Zadanie - problem plecakowy

Ultraszybki serwer VPS NVMe START
0 głosów
84 wizyt
pytanie zadane 4 dni temu w Java przez barteku12 Użytkownik (800 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ź 4 dni temu przez Aisekai Pasjonat (15,960 p.)
wybrane 4 dni temu 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ź 4 dni temu przez obl Nałogowiec (35,530 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 4 dni temu przez barteku12 Użytkownik (800 p.)
Nie rozumiem, gdzie tam jest dzielenie jakieś? Bo ja nie widzę.
komentarz 4 dni temu przez Aisekai Pasjonat (15,960 p.)
edycja 4 dni temu 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 4 dni temu przez obl Nałogowiec (35,530 p.)
W treści zadania nie zauważyłem ani słowa o tym, że to ma być zrobione metodą brutal-force.
komentarz 4 dni temu przez Aisekai Pasjonat (15,960 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ź 58 wizyt
pytanie zadane 28 grudnia 2016 w C# i .NET przez Kobis Nowicjusz (120 p.)
0 głosów
2 odpowiedzi 156 wizyt
pytanie zadane 6 maja w C i C++ przez Barteck125 Obywatel (1,100 p.)
0 głosów
1 odpowiedź 94 wizyt

41,282 zapytań

80,223 odpowiedzi

158,700 komentarzy

19,710 pasjonatów

Przeglądających: 295
Pasjonatów: 29 Gości: 266

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.

...