Porównaj różne algorytmy rozwiązujące dyskretny problem plecakowy w javie.
#1 Gość_Karis126_*
Napisano 21.11.2016 - 09:47
Napisano 25.09.2011 - 17:55
#2
Napisano 21.11.2016 - 20:23
No i gdzie masz te programy?
Jeśli rzuciłem choć promyczek światła na problem który postawiłeś - podziękuj. Nad kreską
#4 Gość_Karis126_*
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
#5
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"; }
Jeśli rzuciłem choć promyczek światła na problem który postawiłeś - podziękuj. Nad kreską