• 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
605 wizyt
pytanie zadane 14 listopada 2017 w Java przez barteku12 Obywatel (1,080 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 (26,950 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,620 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,080 p.)
Nie rozumiem, gdzie tam jest dzielenie jakieś? Bo ja nie widzę.
komentarz 14 listopada 2017 przez Aisekai Nałogowiec (26,950 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,620 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 (26,950 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ź 82 wizyt
pytanie zadane 28 grudnia 2016 w C# i .NET przez Kobis Nowicjusz (120 p.)
0 głosów
2 odpowiedzi 345 wizyt
pytanie zadane 6 maja 2017 w C i C++ przez Barteck125 Obywatel (1,140 p.)
0 głosów
1 odpowiedź 139 wizyt
Porady nie od parady
Pytania na temat serwisu SPOJ należy zadawać z odpowiednią kategorią dotyczącą tej strony.SPOJ

54,403 zapytań

98,275 odpowiedzi

202,122 komentarzy

26,716 pasjonatów

Przeglądających: 311
Pasjonatów: 20 Gości: 291

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.

...