Skocz do zawartości

  •  
  • Mini kompendium
  • MimeTeX
  • Regulamin

Zdjęcie
        STUDIA        

dyskretny problem plecakowy - JAVA



  • Nie możesz napisać tematu
  • Zaloguj się aby odpowiedzieć
4 odpowiedzi w tym temacie

#1 Karis126

Karis126

    Pierwsza pochodna

  • Użytkownik
  • 84 postów
0
Neutralny
  • Płeć:Mężczyzna

Napisano 21.11.2016 - 09:47

Porównaj różne algorytmy rozwiązujące dyskretny problem plecakowy w javie.


  • 0

Afroman

    Kombinator

  • Użytkownik
3
  • Płeć:Kobieta

Napisano 25.09.2011 - 17:55

#2 Jarekzulus

Jarekzulus

    Wielki Analityk

  • +Mods
  • Redaktor
  • 3295 postów
2776
Profesor
  • Płeć:Mężczyzna

Napisano 21.11.2016 - 20:23

No i gdzie masz te programy?


  • 0

:wave: :wave: :wave: Jeśli rzuciłem choć promyczek światła na problem który postawiłeś - podziękuj. pre_1433974176__syg.jpgNad kreską


#3 niki87

niki87

    zła i wredna :)

  • $Jr Admin
  • Redaktor
  • 5936 postów
1508
Starszy Wykładowca II
  • Płeć:Kobieta

Napisano 22.11.2016 - 05:47

chyba, że chodzi o porównanie dowolnych... ale jest ich naprawdę mnóstwo, więc lepiej jakby autor się wysylił i wybrał jakieś algorytmy do porównania


  • 0

MimeTex
Regulamin
Klikając Dołączona grafika mówisz DZIĘKUJĘ


#4 Karis126

Karis126

    Pierwsza pochodna

  • Użytkownik
  • 84 postów
0
Neutralny
  • Płeć:Mężczyzna

Napisano 22.11.2016 - 07:17

trzeba napisać program który używa 4 różnych algorytmów i porównać ich czas działania


  • 0

#5 Jarekzulus

Jarekzulus

    Wielki Analityk

  • +Mods
  • Redaktor
  • 3295 postów
2776
Profesor
  • Płeć:Mężczyzna

Napisano 24.11.2016 - 08:42

Mógłbyś coś napisać - nawet jesli było by źle zadanie by ruszyło

 

Algorytm 1

import java.util.*;
import java.util.Scanner;
import java.io.*;

class PakowaniePlecaka {
    public int[] tab;
    public int dlugosc;
    public int poj;
    
    public PakowaniePlecaka(int ilosc,int pojemnosc) {
        tab = new int[ilosc];
        dlugosc = ilosc;
        poj = pojemnosc;
    }
    
    public void wczytaj() {
        for(int i = 0; i < dlugosc; i++) {
            System.out.println("Podaj element nr " + ( i + 1 ));
            Scanner element = new Scanner(System.in);
            tab[i] = element.nextInt();
        }
   }

    public void wypisz() {
        System.out.print("Zawartość tablicy = ");
        for(int i = 0;i < dlugosc; i++) {
            System.out.print(tab[i] + " ");
        }
        System.out.println();
        System.out.println("Waga jaka się zmieści do plecaka = "+poj);
    }

    /**
     * Algorytm opiera się na wywoływaniu rekurencyjnym zmniejszającym pojemność plecaka
     *
     **/
    public String plecak(int waga, int pocz) {
        String temp = "";
        for(int i = pocz ; i < tab.length ; i++) {//iteracja tablicy od pocz
            if(tab[i] == waga) {
                return String.valueOf(tab[i]);//jezeli trafilismy z waga to zwracamy wartosc
            } else if(waga > tab[i]) {//jezeli waga byla by mniejsza niz aktualny element to nie ma co sprawdzac dalej
                temp = plecak(waga - tab[i], i + 1);//zobaczymy co zwroca pozostale iteracje tablicy
                if(!temp.contains("Brak rozwiazań!")) {
                    return String.valueOf(tab[i]) + " " + temp;//jezeli zwrocone wartosci nie zawieraja 'brak rozwiazan' to znaczy ze trafilismy na wynik, podaj dalej
                }
            }
        }
        return "Brak rozwiazań!";
    }
}

class Plecak {

    public static void main(String[] args) {
        int pojemnosc;
        int ilosc;
        Scanner sc = null;
        while(true) {
            System.out.println("Podaj pojemność plecaka");
            System.out.println("Żeby zakończyć podaj pojemność ujemną lub równą zero");
            sc = new Scanner(System.in);
            pojemnosc = sc.nextInt();
            if(pojemnosc <= 0) break;
            System.out.println("Podaj ilość elementów");
            sc = new Scanner(System.in);
            ilosc = sc.nextInt();
            PakowaniePlecaka p = new PakowaniePlecaka(ilosc,pojemnosc);
            System.out.println();
            p.wczytaj();
            System.out.println();
            p.wypisz();
            System.out.println("Wynik = " + p.plecak(pojemnosc,0));
            System.out.println();
        }
    }
}

Algorytm 2

 public String plecak(int waga, int pocz) {
        String temp = "";
        for(int i = pocz ; i < tab.length ; i++) {  //tab[] przechowuje kolejne wagi
            if(tab[i] == waga) {
                return String.valueOf(tab[i]);
            } else if(waga > tab[i]) {
                temp = plecak(waga - tab[i], i + 1);
                if(!temp.equals("BRAK")) {
                    return String.valueOf(tab[i]) + " " + temp;
                }
            }
        }
        return "BRAK";
    }

  • 0

:wave: :wave: :wave: Jeśli rzuciłem choć promyczek światła na problem który postawiłeś - podziękuj. pre_1433974176__syg.jpgNad kreską