Czy ten program napisany jest metodą zachłanna?

Odpowiedz Nowy wątek
2015-02-04 14:12
Hoopgh
0

Treść zadania jest taka:
Dany jest zbiór 10 liczb.Progam ma wybierac najwiekszy w sensie liczebnosci podzbior tego zbioru ale taki ze suma elementów tego podzbioru nie moze być wieksza od 20.uzyj aogorytmu zachłannego który konstrujać podzbiór zawsze wybiera liczby najmniejsze z jeszcze dostepnych.

public static void main(String[] args) {
        int[] tab = {2, 4, 6, 3, 5, 4, 1, 7, 2, 3};
        //sortowanie
        for (int i = 0; i < tab.length; i++) {
            System.out.print(tab[i]+" ");

        }
        for (int i = 0; i < tab.length; i++) {
            int tmp = tab[i];
            int j = i;
            while (j > 0 && tab[j - 1] > tmp) {
                tab[j] = tab[j - 1];
                j--;
            }
            tab[j] = tmp;  
        }System.out.println();
        for (int i = 0; i < tab.length; i++) {
            System.out.print(tab[i]+" ");

        }

        int s = 0;

        System.out.println("Najwiekszy podzbiór: ");
         for(int i=0;i<tab.length;i++){
            s=s+tab[i];
            if(s<=20){
                System.out.print(tab[i]+", ");
            }

        }
    }
edytowany 1x, ostatnio: bogdans, 2016-12-13 18:26
!Wstawiaj kod w znaczniki &lt;code=java&gt;&lt;/code&gt; - bogdans 2015-02-04 14:49

Pozostało 580 znaków

2015-02-04 14:53
0

Ten program nie robi tego co ma. Polecenie:

Progam ma wybierac najwiekszy w sensie liczebnosci podzbior tego zbioru
zamiast tego, program wypisuje sumę tego największego podzbioru ten podzbiór.
Prościej można posortować tak:

Arrays.sort(tab);

To smutne, że głupcy są tak pewni siebie, a ludzie mądrzy - tak pełni wątpliwości. Bertrand Russell
edytowany 2x, ostatnio: bogdans, 2015-02-04 15:16

Pozostało 580 znaków

2015-02-04 15:13
Hoopgh
0

Piersze program sortuje ten zbiór nastepnie sumuje aż warunek bedzie prawdziwy czyli suma bedzie <=20 i wypisuje te liczby
Oto wynik
2 4 6 3 5 4 1 7 2 3
1 2 2 3 3 4 4 5 6 7 Najwiekszy podzbiór:
1, 2, 2, 3, 3, 4, 4, BUILD SUCCESSFUL (total time: 0 seconds)

Pozostało 580 znaków

2015-02-04 15:22
0

Zgoda, program wypisuje liczby na ekranie. Ale polecenie brzmi

Progam ma wybierac najwiekszy w sensie liczebnosci podzbior tego zbioru
. A tego zbioru nie ma, jest tylko informacja na ekranie o elementach tego zbioru.


To smutne, że głupcy są tak pewni siebie, a ludzie mądrzy - tak pełni wątpliwości. Bertrand Russell

Pozostało 580 znaków

2015-02-04 15:22
Hoopgh
0

Chyba że ta wersja jest lepsza i czy jest użyta metoda zachłanna?

public static void main(String[] args) {
        int[] dane = {2, 4, 6, 3, 5, 4, 1, 7, 2, 3};
        int[] zbiorWyjsciowy;
        int MAX_SUMA = 20;
        int zebranaSuma = 0;
        Arrays.sort(dane);
        int licznik = 0;
        for (int i = 0; i < dane.length; i++) {
            if ((zebranaSuma += dane[i]) <= MAX_SUMA) {
                licznik++;
            } else {
                break;
            }
        }
        zbiorWyjsciowy = Arrays.copyOf(dane, licznik);
        for (int x : zbiorWyjsciowy) {
            System.out.print(x + " ");
        }

    }
edytowany 1x, ostatnio: bogdans, 2016-12-13 18:26

Pozostało 580 znaków

2015-02-04 15:23
Hoopgh
0

W sumie racja to może jakaś podpowiedz jak to zrobić..

Pozostało 580 znaków

2015-02-05 11:21
0

Ja bym go uznał za zachłanny. Czy jest poprawny, czy nie, to zależy od tego, co autor zadania uważa za zbiór. Formalnie rzecz biorąc, w zbiorze każdy element (każda liczba) może wystąpić tylko raz. Ani dane wejściowe, ani Twoje rozwiązanie nie spełniają tego warunku.


To smutne, że głupcy są tak pewni siebie, a ludzie mądrzy - tak pełni wątpliwości. Bertrand Russell

Pozostało 580 znaków

Odpowiedz
Liczba odpowiedzi na stronę

1 użytkowników online, w tym zalogowanych: 0, gości: 1, botów: 0