Przeczytaj

Implementacja rozwiązań różnych wariantów problemu plecakowego w języku Java

Ważne!

W kolejnych implementacjach wykorzystamy funkcję pomocniczą sortuj, której zadaniem jest posortowanie dostępnych przedmiotów nierosnąco ze względu na iloraz wartości oraz wag. Użyjemy zmodyfikowanego algorytmu sortowania bąbelkowegoPxgkD2R5Ysortowania bąbelkowego (nie będziemy go tu omawiać).

public static void sortuj(double[] wartoscDoWagi, Integer[] indeksy, int n) {
	for (int i = 0; i < n - 1; i++) {
		for (int j = 0; j < n - i - 1; j++) {
			if (wartoscDoWagi[j] < wartoscDoWagi[j + 1]) {
				double tempWartosc = wartoscDoWagi[j];
				wartoscDoWagi[j] = wartoscDoWagi[j + 1];
				wartoscDoWagi[j + 1] = tempWartosc;

				int tempIndeks = indeksy[j];
				indeksy[j] = indeksy[j + 1];
				indeksy[j + 1] = tempIndeks;
			}
		}
	}
}

Ważne!

Podejście zachłannealgorytm zachłannyzachłanne może nie dać najlepszego możliwego wyniku w wypadku problemu plecakowego.

Ogólny problem plecakowy

Specyfikacja problemu:

Dane:

nazwy – tablica liczb łańcuchów znaków; nazwy poszczególnych przedmiotów
wartosci – tablica liczb naturalnych; wartości poszczególnych przedmiotów
wagi – tablica liczb naturalnych; wagi poszczególnych przedmiotów
n – liczba naturalna; liczba rodzajów przedmiotów
pojemnosc – liczba naturalna; maksymalna pojemność plecaka

Wynik:

liczby sztuk poszczególnych przedmiotów (również równe 0), których całkowita waga nie przekracza wartości przechowywanej w zmiennej pojemnosc, a których całkowita wartość jest największa wśród możliwych wypełnień plecaka rzeczami o takiej wadze, która nie przekracza wartości zmiennej pojemnosc
całkowita wartość spakowanego plecaka

Zaprezentowane rozwiązania będziemy testować dla następujących danych:

maksymalna pojemność plecaka wynosi 41;
do dyspozycji mamy nieograniczoną liczbę sztuk każdego rodzaju przedmiotów;
przedmioty mają następujące wartości oraz wagi:

Przedmiot – $i$	0	1	2	3	4	5	6
Nazwa	anemon	bławatek	chaber	dziurawiec	eustoma	forsycja	gipsówka
Wartość	21	15	4	4	14	1	3
Waga	11	8	5	4	7	1	7

Już wiesz

Przypomnijmy, w jaki sposób działa algorytm, analizując zaprezentowane dane.

Zaczniemy od obliczenia ilorazów wartości i wag.

Obliczone ilorazy: 21/11, 15/8, 4/5, 4/4, 14/7, 1/1, 3/7.

Sortujemy je nierosnąco.

Posortowane nierosnąco ilorazy: 14/7, 21/11, 15/8, 4/4, 1/1, 4/5, 3/7.

Daje to następującą kolejność posortowanych nierosnąco przedmiotów: eustoma, anemon, bławatek, dziurawiec, forsycja, chaber, gipsówka (indeksy: 4, 0, 1, 3, 5, 2, 6).

Dla każdego posortowanego przedmiotu sprawdzamy, czy można go spakować, a jeśli tak, ile sztuk.

Wybieramy pierwszy przedmiot. To eustoma, której waga to 7. Do plecaka wkładamy 5 sztuk tego przedmiotu. Pojemność plecaka po spakowaniu tych przedmiotów wynosi 6.

Waga kolejnego przedmiotu (anemonu) wynosi 11, zatem nie można go spakować do plecaka.

Następny przedmiot, bławatek, waży 8. On również nie może zostać spakowany do plecaka.

Kolejny przedmiot to dziurawiec. Jego waga wynosi 4, zatem do plecaka można spakować jego jedną sztukę. Po spakowaniu kolejnych przedmiotów pojemność plecaka wynosi 2.

Następnym przedmiotem jest forsycja. Jej waga to 1. Do plecaka pakujemy jej dwie sztuki.

W plecaku nie ma więcej miejsca, zatem kolejne przedmioty nie mogą zostać spakowane.

Obliczmy całkowitą wartość spakowanych przedmiotów:

eustoma: 14 × 5 sztuk
dziurawiec: 1 × 4 sztuki
forsycja: 2 × 1 sztuka

Całkowita wartość spakowanych przedmiotów wynosi 76. Wykorzystaliśmy całe miejsce.

W programie wykorzystamy dwie funkcje:

ogolnyPlecak – funkcja mająca na celu znalezienie największej łącznej wartości przedmiotów, które można zmieścić w plecaku o określonej pojemności z wykorzystaniem podejścia zachłannego;
sortuj – funkcja pomocnicza.

Jak wspomnieliśmy, nie będziemy omawiać funkcji sortuj. Przejdziemy zatem do zapisania funkcji właściwej.

Zapisujemy jej nagłówek. Funkcja przyjmie pięć argumentów:

nazwy – tablica łańcuchów znaków; nazwy poszczególnych przedmiotów,
wartosci – tablica liczb naturalnych; wartości poszczególnych przedmiotów,
wagi – tablica liczb naturalnych; wagi poszczególnych przedmiotów,
n – liczba naturalna; liczba rodzajów przedmiotów,
pojemnosc – liczba naturalna; maksymalna pojemność plecaka.

public static void ogolnyPlecak(String[] nazwy, int[] wartosci, int[] wagi, int n, int pojemnosc) {

}

W pierwszym kroku tworzone są dwie kolejne tablice:

wartoscDoWagi – tablica liczb rzeczywistych,
indeksy – tablica liczb naturalnych.

Obie tablice składają się z n elementów. Zapisujemy pętlę for, która będzie iterować po kolejnych elementach tablic, by je zapełnić.

Każdy i-ty element tablicy wartosci dzielimy przez i-ty element tablicy wagi. Wynik przypisujemy do i-tego elementu tablicy wartoscDoWagi. Następnie i-temu elementowi tablicy indeksy przypisujemy wartość licznika, czyli zmiennej i.

public static void ogolnyPlecak(String[] nazwy, int[] wartosci, int[] wagi, int n, int pojemnosc) {
	double[] wartoscDoWagi = new double[n];
	int[] indeksy = new int[n];
	for (int i = 0; i < n; i++) {
		wartoscDoWagi[i] = (double) wartosci[i] / wagi[i];
		indeksy[i] = i;
	}
}

Po wyjściu z pętli wywołujemy funkcję sortuj.

Funkcja sortuj przyjmuje trzy argumenty:

wartoscDoWagi – tablica liczb rzeczywistych,
indeksy – tablica liczb naturalnych,
n – liczba naturalna.

public static void ogolnyPlecak(String[] nazwy, int[] wartosci, int[] wagi, int n, int pojemnosc) {
	double[] wartoscDoWagi = new double[n];
	int[] indeksy = new int[n];
	for (int i = 0; i < n; i++) {
		wartoscDoWagi[i] = (double) wartosci[i] / wagi[i];
		indeksy[i] = i;
	}

	sortuj(wartoscDoWagi, indeksy, n);
}

Po wykonaniu sortowania tworzymy zmienną wynik i przypisujemy jej wartość 0. Zmienna ta będzie przechowywała sumę wartości wybranych przedmiotów.

Tworzymy również tablicę spakowane. Będzie przechowywała liczniki spakowanych przedmiotów.

W kolejnym kroku zapisujemy pętlę for, która będzie iterowała przez posortowane przedmioty. Wykorzystamy ją do wypełnienia tablicy spakowane zerami.

Zapisujemy kolejną pętlę for. Ponownie iterujemy przez posortowane przedmioty.

W pętli utworzymy zmienną indeks, której z każdą iteracją będziemy przypisywać wartość i-tego elementu tablicy indeksy – pobieramy w ten sposób indeks bieżącego przedmiotu.

Zapisujemy pętlę while. Będzie ona wykonywała się tak długo, jak długo waga pakowanego przedmiotu będzie albo mniejsza od pojemności, albo jej równa. Dzięki tej pętli kolejne przedmioty będą mogły być dodawane więcej niż jeden raz.

public static void ogolnyPlecak(String[] nazwy, int[] wartosci, int[] wagi, int n, int pojemnosc) {
	double[] wartoscDoWagi = new double[n];
	int[] indeksy = new int[n];
	for (int i = 0; i < n; i++) {
		wartoscDoWagi[i] = (double) wartosci[i] / wagi[i];
		indeksy[i] = i;
	}

	sortuj(wartoscDoWagi, indeksy, n);

	int wynik = 0;
	int[] spakowane = new int[n];

	for (int i = 0; i < n; i++) {
		spakowane[i] = 0;
	}

	for (int i = 0; i < n; i++) {
		int indeks = indeksy[i];
		while (wagi[indeks] <= pojemnosc) {
		}
	}
}

Jeśli przedmiot o danym indeksie zmieści się w plecaku, waga przedmiotu odejmowana jest od dostępnej pojemności plecaka (element tablicy wagi o indeksie indeks jest odejmowany od wartości zmiennej pojemnosc). Równocześnie dodajemy wartość tego przedmiotu do wyniku (element tablicy wartosci o indeksie indeks jest dodawany do wartości zmiennej wynik). Inkrementujemy wartość elementu tablicy spakowane o indeksie indeks.

Linia 1. public static void ogolnyPlecak otwórz nawias okrągły String otwórz nawias kwadratowy zamknij nawias kwadratowy nazwy przecinek int otwórz nawias kwadratowy zamknij nawias kwadratowy wartosci przecinek int otwórz nawias kwadratowy zamknij nawias kwadratowy wagi przecinek int n przecinek int pojemnosc zamknij nawias okrągły otwórz nawias klamrowy. Linia 2. double otwórz nawias kwadratowy zamknij nawias kwadratowy wartoscDoWagi znak równości new double otwórz nawias kwadratowy n zamknij nawias kwadratowy średnik. Linia 3. int otwórz nawias kwadratowy zamknij nawias kwadratowy indeksy znak równości new int otwórz nawias kwadratowy n zamknij nawias kwadratowy średnik. Linia 4. for otwórz nawias okrągły int i znak równości 0 średnik i otwórz nawias ostrokątny n średnik i plus plus zamknij nawias okrągły otwórz nawias klamrowy. Linia 5. wartoscDoWagi otwórz nawias kwadratowy i zamknij nawias kwadratowy znak równości otwórz nawias okrągły double zamknij nawias okrągły wartosci otwórz nawias kwadratowy i zamknij nawias kwadratowy prawy ukośnik wagi otwórz nawias kwadratowy i zamknij nawias kwadratowy średnik. Linia 6. indeksy otwórz nawias kwadratowy i zamknij nawias kwadratowy znak równości i średnik. Linia 7. zamknij nawias klamrowy. Linia 9. sortuj otwórz nawias okrągły wartoscDoWagi przecinek indeksy przecinek n zamknij nawias okrągły średnik. Linia 11. int wynik znak równości 0 średnik. Linia 12. int otwórz nawias kwadratowy zamknij nawias kwadratowy spakowane znak równości new int otwórz nawias kwadratowy n zamknij nawias kwadratowy średnik. Linia 14. for otwórz nawias okrągły int i znak równości 0 średnik i otwórz nawias ostrokątny n średnik i plus plus zamknij nawias okrągły otwórz nawias klamrowy. Linia 15. spakowane otwórz nawias kwadratowy i zamknij nawias kwadratowy znak równości 0 średnik. Linia 16. zamknij nawias klamrowy. Linia 18. for otwórz nawias okrągły int i znak równości 0 średnik i otwórz nawias ostrokątny n średnik i plus plus zamknij nawias okrągły otwórz nawias klamrowy. Linia 19. int indeks znak równości indeksy otwórz nawias kwadratowy i zamknij nawias kwadratowy średnik. Linia 20. while otwórz nawias okrągły wagi otwórz nawias kwadratowy indeks zamknij nawias kwadratowy otwórz nawias ostrokątny znak równości pojemnosc zamknij nawias okrągły otwórz nawias klamrowy. Linia 21. pojemnosc minus znak równości wagi otwórz nawias kwadratowy indeks zamknij nawias kwadratowy średnik. Linia 22. wynik plus znak równości wartosci otwórz nawias kwadratowy indeks zamknij nawias kwadratowy średnik. Linia 23. spakowane otwórz nawias kwadratowy indeks zamknij nawias kwadratowy plus plus średnik. Linia 24. zamknij nawias klamrowy. Linia 25. zamknij nawias klamrowy. Linia 26. zamknij nawias klamrowy.

public static void ogolnyPlecak(String[] nazwy, int[] wartosci, int[] wagi, int n, int pojemnosc) {
	double[] wartoscDoWagi = new double[n];
	int[] indeksy = new int[n];
	for (int i = 0; i < n; i++) {
		wartoscDoWagi[i] = (double) wartosci[i] / wagi[i];
		indeksy[i] = i;
	}

	sortuj(wartoscDoWagi, indeksy, n);

	int wynik = 0;
	int[] spakowane = new int[n];

	for (int i = 0; i < n; i++) {
		spakowane[i] = 0;
	}

	for (int i = 0; i < n; i++) {
		int indeks = indeksy[i];
		while (wagi[indeks] <= pojemnosc) {
			pojemnosc -= wagi[indeks];
			wynik += wartosci[indeks];
			spakowane[indeks]++;
		}
	}
}

Po wyjściu z pętli for zapisujemy kolejną pętlę for. Wykorzystamy ją do wypisywania informacji na temat tego, ile sztuk danego rodzaju przedmiotu zostało spakowanych.

Wypisujemy całkowitą wartość spakowanych przedmiotów.

public static void ogolnyPlecak(String[] nazwy, int[] wartosci, int[] wagi, int n, int pojemnosc) {
	double[] wartoscDoWagi = new double[n];
	int[] indeksy = new int[n];
	for (int i = 0; i < n; i++) {
		wartoscDoWagi[i] = (double) wartosci[i] / wagi[i];
		indeksy[i] = i;
	}

	sortuj(wartoscDoWagi, indeksy, n);

	int wynik = 0;
	int[] spakowane = new int[n];

	for (int i = 0; i < n; i++) {
		spakowane[i] = 0;
	}

	for (int i = 0; i < n; i++) {
		int indeks = indeksy[i];
		while (wagi[indeks] <= pojemnosc) {
			pojemnosc -= wagi[indeks];
			wynik += wartosci[indeks];
			spakowane[indeks]++;
		}
	}

	for (int i = 0; i < n; i++) {
		System.out.println("Liczba spakowanych sztuk przedmiotu " + nazwy[i] + " (indeks " + i + "): " + spakowane[i]);
	}

	System.out.println("\nWartosc spakowanych przedmiotow: " + wynik);
}

Dodajemy odpowiednią bibliotekę oraz wywołanie funkcji.

Pamiętamy również o komunikacie dotyczącym wartości wszystkich spakowanych przedmiotów oraz dodaniu funkcji sortuj.

Oto kompletny kod programu:

Linia 1. import java kropka util kropka Arrays średnik. Linia 3. public class Main otwórz nawias klamrowy. Linia 4. public static void sortuj otwórz nawias okrągły double otwórz nawias kwadratowy zamknij nawias kwadratowy wartoscDoWagi przecinek int otwórz nawias kwadratowy zamknij nawias kwadratowy indeksy przecinek int n zamknij nawias okrągły otwórz nawias klamrowy. Linia 5. for otwórz nawias okrągły int i znak równości 0 średnik i otwórz nawias ostrokątny n minus 1 średnik i plus plus zamknij nawias okrągły otwórz nawias klamrowy. Linia 6. for otwórz nawias okrągły int j znak równości 0 średnik j otwórz nawias ostrokątny n minus i minus 1 średnik j plus plus zamknij nawias okrągły otwórz nawias klamrowy. Linia 7. if otwórz nawias okrągły wartoscDoWagi otwórz nawias kwadratowy j zamknij nawias kwadratowy otwórz nawias ostrokątny wartoscDoWagi otwórz nawias kwadratowy j plus 1 zamknij nawias kwadratowy zamknij nawias okrągły otwórz nawias klamrowy. Linia 8. double tempWartosc znak równości wartoscDoWagi otwórz nawias kwadratowy j zamknij nawias kwadratowy średnik. Linia 9. wartoscDoWagi otwórz nawias kwadratowy j zamknij nawias kwadratowy znak równości wartoscDoWagi otwórz nawias kwadratowy j plus 1 zamknij nawias kwadratowy średnik. Linia 10. wartoscDoWagi otwórz nawias kwadratowy j plus 1 zamknij nawias kwadratowy znak równości tempWartosc średnik. Linia 12. int tempIndeks znak równości indeksy otwórz nawias kwadratowy j zamknij nawias kwadratowy średnik. Linia 13. indeksy otwórz nawias kwadratowy j zamknij nawias kwadratowy znak równości indeksy otwórz nawias kwadratowy j plus 1 zamknij nawias kwadratowy średnik. Linia 14. indeksy otwórz nawias kwadratowy j plus 1 zamknij nawias kwadratowy znak równości tempIndeks średnik. Linia 15. zamknij nawias klamrowy. Linia 16. zamknij nawias klamrowy. Linia 17. zamknij nawias klamrowy. Linia 18. zamknij nawias klamrowy. Linia 20. public static void ogolnyPlecak otwórz nawias okrągły String otwórz nawias kwadratowy zamknij nawias kwadratowy nazwy przecinek int otwórz nawias kwadratowy zamknij nawias kwadratowy wartosci przecinek int otwórz nawias kwadratowy zamknij nawias kwadratowy wagi przecinek int n przecinek int pojemnosc zamknij nawias okrągły otwórz nawias klamrowy. Linia 21. double otwórz nawias kwadratowy zamknij nawias kwadratowy wartoscDoWagi znak równości new double otwórz nawias kwadratowy n zamknij nawias kwadratowy średnik. Linia 22. int otwórz nawias kwadratowy zamknij nawias kwadratowy indeksy znak równości new int otwórz nawias kwadratowy n zamknij nawias kwadratowy średnik. Linia 23. for otwórz nawias okrągły int i znak równości 0 średnik i otwórz nawias ostrokątny n średnik i plus plus zamknij nawias okrągły otwórz nawias klamrowy. Linia 24. wartoscDoWagi otwórz nawias kwadratowy i zamknij nawias kwadratowy znak równości otwórz nawias okrągły double zamknij nawias okrągły wartosci otwórz nawias kwadratowy i zamknij nawias kwadratowy prawy ukośnik wagi otwórz nawias kwadratowy i zamknij nawias kwadratowy średnik. Linia 25. indeksy otwórz nawias kwadratowy i zamknij nawias kwadratowy znak równości i średnik. Linia 26. zamknij nawias klamrowy. Linia 28. sortuj otwórz nawias okrągły wartoscDoWagi przecinek indeksy przecinek n zamknij nawias okrągły średnik. Linia 30. int wynik znak równości 0 średnik. Linia 31. int otwórz nawias kwadratowy zamknij nawias kwadratowy spakowane znak równości new int otwórz nawias kwadratowy n zamknij nawias kwadratowy średnik. Linia 33. for otwórz nawias okrągły int i znak równości 0 średnik i otwórz nawias ostrokątny n średnik i plus plus zamknij nawias okrągły otwórz nawias klamrowy. Linia 34. spakowane otwórz nawias kwadratowy i zamknij nawias kwadratowy znak równości 0 średnik. Linia 35. zamknij nawias klamrowy. Linia 37. for otwórz nawias okrągły int i znak równości 0 średnik i otwórz nawias ostrokątny n średnik i plus plus zamknij nawias okrągły otwórz nawias klamrowy. Linia 38. int indeks znak równości indeksy otwórz nawias kwadratowy i zamknij nawias kwadratowy średnik. Linia 39. while otwórz nawias okrągły wagi otwórz nawias kwadratowy indeks zamknij nawias kwadratowy otwórz nawias ostrokątny znak równości pojemnosc zamknij nawias okrągły otwórz nawias klamrowy. Linia 40. pojemnosc minus znak równości wagi otwórz nawias kwadratowy indeks zamknij nawias kwadratowy średnik. Linia 41. wynik plus znak równości wartosci otwórz nawias kwadratowy indeks zamknij nawias kwadratowy średnik. Linia 42. spakowane otwórz nawias kwadratowy indeks zamknij nawias kwadratowy plus plus średnik. Linia 43. zamknij nawias klamrowy. Linia 44. zamknij nawias klamrowy. Linia 46. for otwórz nawias okrągły int i znak równości 0 średnik i otwórz nawias ostrokątny n średnik i plus plus zamknij nawias okrągły otwórz nawias klamrowy. Linia 47. System kropka out kropka println otwórz nawias okrągły cudzysłów Liczba spakowanych sztuk przedmiotu cudzysłów plus nazwy otwórz nawias kwadratowy i zamknij nawias kwadratowy plus cudzysłów otwórz nawias okrągły indeks cudzysłów plus i plus cudzysłów zamknij nawias okrągły dwukropek cudzysłów plus spakowane otwórz nawias kwadratowy i zamknij nawias kwadratowy zamknij nawias okrągły średnik. Linia 48. zamknij nawias klamrowy. Linia 50. System kropka out kropka println otwórz nawias okrągły cudzysłów lewy ukośnik nWartosc spakowanych przedmiotow dwukropek cudzysłów plus wynik zamknij nawias okrągły średnik. Linia 51. zamknij nawias klamrowy. Linia 53. public static void main otwórz nawias okrągły String otwórz nawias kwadratowy zamknij nawias kwadratowy args zamknij nawias okrągły otwórz nawias klamrowy. Linia 54. String otwórz nawias kwadratowy zamknij nawias kwadratowy nazwy znak równości otwórz nawias klamrowy cudzysłów anemon cudzysłów przecinek cudzysłów bławatek cudzysłów przecinek cudzysłów chaber cudzysłów przecinek cudzysłów dziurawiec cudzysłów przecinek cudzysłów eustoma cudzysłów przecinek cudzysłów forsycja cudzysłów przecinek cudzysłów gipsówka cudzysłów zamknij nawias klamrowy średnik. Linia 55. int otwórz nawias kwadratowy zamknij nawias kwadratowy wartosci znak równości otwórz nawias klamrowy 21 przecinek 15 przecinek 4 przecinek 4 przecinek 14 przecinek 1 przecinek 3 zamknij nawias klamrowy średnik. Linia 56. int otwórz nawias kwadratowy zamknij nawias kwadratowy wagi znak równości otwórz nawias klamrowy 11 przecinek 8 przecinek 5 przecinek 4 przecinek 7 przecinek 1 przecinek 7 zamknij nawias klamrowy średnik. Linia 57. int n znak równości 7 średnik. Linia 58. int pojemnosc znak równości 41 średnik. Linia 60. ogolnyPlecak otwórz nawias okrągły nazwy przecinek wartosci przecinek wagi przecinek n przecinek pojemnosc zamknij nawias okrągły średnik. Linia 61. zamknij nawias klamrowy. Linia 62. zamknij nawias klamrowy.

import java.util.Arrays;

public class Main {
    public static void sortuj(double[] wartoscDoWagi, int[] indeksy, int n) {
        for (int i = 0; i < n - 1; i++) {
            for (int j = 0; j < n - i - 1; j++) {
                if (wartoscDoWagi[j] < wartoscDoWagi[j + 1]) {
                    double tempWartosc = wartoscDoWagi[j];
                    wartoscDoWagi[j] = wartoscDoWagi[j + 1];
                    wartoscDoWagi[j + 1] = tempWartosc;

                    int tempIndeks = indeksy[j];
                    indeksy[j] = indeksy[j + 1];
                    indeksy[j + 1] = tempIndeks;
                }
            }
        }
    }

    public static void ogolnyPlecak(String[] nazwy, int[] wartosci, int[] wagi, int n, int pojemnosc) {
        double[] wartoscDoWagi = new double[n];
        int[] indeksy = new int[n];
        for (int i = 0; i < n; i++) {
            wartoscDoWagi[i] = (double) wartosci[i] / wagi[i];
            indeksy[i] = i;
        }

        sortuj(wartoscDoWagi, indeksy, n);

        int wynik = 0;
        int[] spakowane = new int[n];

        for (int i = 0; i < n; i++) {
            spakowane[i] = 0;
        }

        for (int i = 0; i < n; i++) {
            int indeks = indeksy[i];
            while (wagi[indeks] <= pojemnosc) {
                pojemnosc -= wagi[indeks];
                wynik += wartosci[indeks];
                spakowane[indeks]++;
            }
        }

        for (int i = 0; i < n; i++) {
            System.out.println("Liczba spakowanych sztuk przedmiotu " + nazwy[i] + " (indeks " + i + "): " + spakowane[i]);
        }

        System.out.println("\nWartosc spakowanych przedmiotow: " + wynik);
    }

    public static void main(String[] args) {
        String[] nazwy = {"anemon", "bławatek", "chaber", "dziurawiec", "eustoma", "forsycja", "gipsówka"};
        int[] wartosci = {21, 15, 4, 4, 14, 1, 3};
        int[] wagi = {11, 8, 5, 4, 7, 1, 7};
        int n = 7;
        int pojemnosc = 41;

        ogolnyPlecak(nazwy, wartosci, wagi, n, pojemnosc);
    }
}

Wynik działania programu:

Liczba spakowanych sztuk przedmiotu anemon (indeks 0): 0
Liczba spakowanych sztuk przedmiotu bławatek (indeks 1): 0
Liczba spakowanych sztuk przedmiotu chaber (indeks 2): 0
Liczba spakowanych sztuk przedmiotu dziurawiec (indeks 3): 1
Liczba spakowanych sztuk przedmiotu eustoma (indeks 4): 5
Liczba spakowanych sztuk przedmiotu forsycja (indeks 5): 2
Liczba spakowanych sztuk przedmiotu gipsówka (indeks 6): 0

Wartosc spakowanych przedmiotow: 76

Decyzyjny problem plecakowy

Specyfikacja problemu:

Dane:

nazwy – tablica liczb łańcuchów znaków; nazwy poszczególnych przedmiotów
wartosci – tablica liczb naturalnych; wartości poszczególnych przedmiotów
wagi – tablica liczb naturalnych; wagi poszczególnych przedmiotów
n – liczba naturalna; liczba rodzajów przedmiotów
pojemnosc – liczba naturalna; maksymalna pojemność plecaka

Wynik:

spakowane przedmioty, których całkowita waga nie przekracza wartości przechowywanej w zmiennej pojemnosc, a których całkowita wartość jest największa wśród możliwych wypełnień plecaka rzeczami o takiej wadze, która nie przekracza wartości zmiennej pojemnosc; pakujemy po jednej sztuce przedmiotu każdego rodzaju
całkowita wartość spakowanego plecaka

Zaprezentowane rozwiązania będziemy testować dla następujących danych:

maksymalna pojemność plecaka wynosi 21;
do dyspozycji mamy po jednej sztuce przedmiotu każdego rodzaju;
przedmioty mają następujące wartości oraz wagi:

Przedmiot – $i$	0	1	2	3	4	5	6
Nazwa	aparat	baterie	czajnik	dmuchany materac	ekologiczny prysznic	filtr	garnuszek
Wartość	4	15	6	13	5	12	3
Waga	8	3	2	6	15	16	2

Pojemność plecaka to 21.

Już wiesz

Przypomnijmy, w jaki sposób działa algorytm, analizując podane dane.

Zaczniemy od obliczenia ilorazów wartości i wag: 4/8, 15/3, 6/2, 13/6, 5/15, 12/16, 3/2.

Sortujemy je nierosnąco.

Posortowane nierosnąco ilorazy: 15/3, 6/2, 13/6, 3/2, 12/16, 4/8, 5/15.

Daje to następującą kolejność posortowanych nierosnąco przedmiotów: baterie, czajnik, dmuchany materac, garnuszek, filtr, aparat, ekologiczny prysznic (indeksy: 1, 2, 3, 6, 5, 0, 4).

Dla każdego posortowanego przedmiotu sprawdzamy, czy można go spakować.

Wybieramy pierwszy przedmiot. To baterie, których waga to 3. Waga jest mniejsza od pojemności, zatem pakujemy je do plecaka. Pojemność plecaka po spakowaniu baterii wynosi 18.

Waga kolejnego przedmiotu (czajnika) wynosi 2, zatem można spakować ten przedmiot. Pojemność plecaka to 16.

Kolejnym przedmiotem jest dmuchany materac. Waga tego przedmiotu to 6. Jest mniejsza od pojemności plecaka, zatem przedmiot zostaje zapakowany. Pozostała pojemność plecaka wynosi 10.

Kolejny przedmiot, garnuszek, waży 2. Może zostać spakowany, a pojemność po jego spakowaniu wynosi 8.

Waga filtra, następnego przedmiotu, wynosi 16. Jest większa od tego, jaka jest pozostała pojemność plecaka, zatem nie można go spakować.

Aparat jest kolejnym przedmiotem, a jego waga wynosi 8. Może zostać spakowany do plecaka.

Wypełniliśmy tym samym całe miejsce w plecaku.

Obliczmy całkowitą wartość spakowanych przedmiotów:

baterie: 15
czajnik: 6
dmuchany materac: 13
garnuszek: 3
aparat: 4

Całkowita wartość spakowanych przedmiotów wynosi 41. Wykorzystaliśmy całe miejsce.

Decyzyjny problem plecakowy wymaga, by każdy przedmiot był dodawany do plecaka maksymalnie jeden raz. W programie wymaga to zmiany niewielkiej części programu.

Konieczne jest pominięcie pętli while w tym fragmencie i wykorzystanie instrukcji warunkowej if:

for (int i = 0; i < n; i++) {
	int indeks = indeksy[i];
	if (wagi[indeks] <= pojemnosc) {
		pojemnosc -= wagi[indeks];
		wynik += wartosci[indeks];
		System.out.println("Spakowano przedmiot " + nazwy[indeks] + " (indeks " + indeks + ")");
        }
    }

Zwróć uwagę, że w kodzie nie pojawia się również tablica spakowane, ponieważ w przypadku problemu decyzyjnego nie ma potrzeby liczenia, ile sztuk danego przedmiotu spakowano (do dyspozycji jest tylko jedna sztuka danego przedmiotu).

Oto kompletny kod programu:

Linia 1. import java kropka util kropka Arrays średnik. Linia 3. public class Main otwórz nawias klamrowy. Linia 4. public static void sortuj otwórz nawias okrągły double otwórz nawias kwadratowy zamknij nawias kwadratowy wartoscDoWagi przecinek int otwórz nawias kwadratowy zamknij nawias kwadratowy indeksy przecinek int n zamknij nawias okrągły otwórz nawias klamrowy. Linia 5. for otwórz nawias okrągły int i znak równości 0 średnik i otwórz nawias ostrokątny n minus 1 średnik i plus plus zamknij nawias okrągły otwórz nawias klamrowy. Linia 6. for otwórz nawias okrągły int j znak równości 0 średnik j otwórz nawias ostrokątny n minus i minus 1 średnik j plus plus zamknij nawias okrągły otwórz nawias klamrowy. Linia 7. if otwórz nawias okrągły wartoscDoWagi otwórz nawias kwadratowy j zamknij nawias kwadratowy otwórz nawias ostrokątny wartoscDoWagi otwórz nawias kwadratowy j plus 1 zamknij nawias kwadratowy zamknij nawias okrągły otwórz nawias klamrowy. Linia 8. double tempWartosc znak równości wartoscDoWagi otwórz nawias kwadratowy j zamknij nawias kwadratowy średnik. Linia 9. wartoscDoWagi otwórz nawias kwadratowy j zamknij nawias kwadratowy znak równości wartoscDoWagi otwórz nawias kwadratowy j plus 1 zamknij nawias kwadratowy średnik. Linia 10. wartoscDoWagi otwórz nawias kwadratowy j plus 1 zamknij nawias kwadratowy znak równości tempWartosc średnik. Linia 12. int tempIndeks znak równości indeksy otwórz nawias kwadratowy j zamknij nawias kwadratowy średnik. Linia 13. indeksy otwórz nawias kwadratowy j zamknij nawias kwadratowy znak równości indeksy otwórz nawias kwadratowy j plus 1 zamknij nawias kwadratowy średnik. Linia 14. indeksy otwórz nawias kwadratowy j plus 1 zamknij nawias kwadratowy znak równości tempIndeks średnik. Linia 15. zamknij nawias klamrowy. Linia 16. zamknij nawias klamrowy. Linia 17. zamknij nawias klamrowy. Linia 18. zamknij nawias klamrowy. Linia 20. public static void decyzyjnyPlecak otwórz nawias okrągły String otwórz nawias kwadratowy zamknij nawias kwadratowy nazwy przecinek int otwórz nawias kwadratowy zamknij nawias kwadratowy wartosci przecinek int otwórz nawias kwadratowy zamknij nawias kwadratowy wagi przecinek int n przecinek int pojemnosc zamknij nawias okrągły otwórz nawias klamrowy. Linia 21. double otwórz nawias kwadratowy zamknij nawias kwadratowy wartoscDoWagi znak równości new double otwórz nawias kwadratowy n zamknij nawias kwadratowy średnik. Linia 22. int otwórz nawias kwadratowy zamknij nawias kwadratowy indeksy znak równości new int otwórz nawias kwadratowy n zamknij nawias kwadratowy średnik. Linia 23. for otwórz nawias okrągły int i znak równości 0 średnik i otwórz nawias ostrokątny n średnik i plus plus zamknij nawias okrągły otwórz nawias klamrowy. Linia 24. wartoscDoWagi otwórz nawias kwadratowy i zamknij nawias kwadratowy znak równości otwórz nawias okrągły double zamknij nawias okrągły wartosci otwórz nawias kwadratowy i zamknij nawias kwadratowy prawy ukośnik wagi otwórz nawias kwadratowy i zamknij nawias kwadratowy średnik. Linia 25. indeksy otwórz nawias kwadratowy i zamknij nawias kwadratowy znak równości i średnik. Linia 26. zamknij nawias klamrowy. Linia 28. sortuj otwórz nawias okrągły wartoscDoWagi przecinek indeksy przecinek n zamknij nawias okrągły średnik. Linia 30. int wynik znak równości 0 średnik. Linia 32. for otwórz nawias okrągły int i znak równości 0 średnik i otwórz nawias ostrokątny n średnik i plus plus zamknij nawias okrągły otwórz nawias klamrowy. Linia 33. int indeks znak równości indeksy otwórz nawias kwadratowy i zamknij nawias kwadratowy średnik. Linia 34. if otwórz nawias okrągły wagi otwórz nawias kwadratowy indeks zamknij nawias kwadratowy otwórz nawias ostrokątny znak równości pojemnosc zamknij nawias okrągły otwórz nawias klamrowy. Linia 35. pojemnosc minus znak równości wagi otwórz nawias kwadratowy indeks zamknij nawias kwadratowy średnik. Linia 36. wynik plus znak równości wartosci otwórz nawias kwadratowy indeks zamknij nawias kwadratowy średnik. Linia 37. System kropka out kropka println otwórz nawias okrągły cudzysłów Spakowano przedmiot cudzysłów plus nazwy otwórz nawias kwadratowy indeks zamknij nawias kwadratowy plus cudzysłów otwórz nawias okrągły indeks cudzysłów plus indeks plus cudzysłów zamknij nawias okrągły cudzysłów zamknij nawias okrągły średnik. Linia 38. zamknij nawias klamrowy. Linia 39. zamknij nawias klamrowy. Linia 41. System kropka out kropka println otwórz nawias okrągły cudzysłów lewy ukośnik nWartosc spakowanych przedmiotow dwukropek cudzysłów plus wynik zamknij nawias okrągły średnik. Linia 42. zamknij nawias klamrowy. Linia 44. public static void main otwórz nawias okrągły String otwórz nawias kwadratowy zamknij nawias kwadratowy args zamknij nawias okrągły otwórz nawias klamrowy. Linia 45. String otwórz nawias kwadratowy zamknij nawias kwadratowy nazwy znak równości otwórz nawias klamrowy cudzysłów aparat cudzysłów przecinek cudzysłów baterie cudzysłów przecinek cudzysłów czajnik cudzysłów przecinek cudzysłów dmuchany materac cudzysłów przecinek cudzysłów ekologiczny prysznic cudzysłów przecinek cudzysłów filtr cudzysłów przecinek cudzysłów garnuszek cudzysłów zamknij nawias klamrowy średnik. Linia 46. int otwórz nawias kwadratowy zamknij nawias kwadratowy wartosci znak równości otwórz nawias klamrowy 4 przecinek 15 przecinek 6 przecinek 13 przecinek 5 przecinek 12 przecinek 3 zamknij nawias klamrowy średnik. Linia 47. int otwórz nawias kwadratowy zamknij nawias kwadratowy wagi znak równości otwórz nawias klamrowy 8 przecinek 3 przecinek 2 przecinek 6 przecinek 15 przecinek 16 przecinek 2 zamknij nawias klamrowy średnik. Linia 48. int n znak równości 7 średnik. Linia 49. int pojemnosc znak równości 21 średnik. Linia 51. decyzyjnyPlecak otwórz nawias okrągły nazwy przecinek wartosci przecinek wagi przecinek n przecinek pojemnosc zamknij nawias okrągły średnik. Linia 52. zamknij nawias klamrowy. Linia 53. zamknij nawias klamrowy.

import java.util.Arrays;

public class Main {
    public static void sortuj(double[] wartoscDoWagi, int[] indeksy, int n) {
        for (int i = 0; i < n - 1; i++) {
            for (int j = 0; j < n - i - 1; j++) {
                if (wartoscDoWagi[j] < wartoscDoWagi[j + 1]) {
                    double tempWartosc = wartoscDoWagi[j];
                    wartoscDoWagi[j] = wartoscDoWagi[j + 1];
                    wartoscDoWagi[j + 1] = tempWartosc;

                    int tempIndeks = indeksy[j];
                    indeksy[j] = indeksy[j + 1];
                    indeksy[j + 1] = tempIndeks;
                }
            }
        }
    }

    public static void decyzyjnyPlecak(String[] nazwy, int[] wartosci, int[] wagi, int n, int pojemnosc) {
        double[] wartoscDoWagi = new double[n];
        int[] indeksy = new int[n];
        for (int i = 0; i < n; i++) {
            wartoscDoWagi[i] = (double) wartosci[i] / wagi[i];
            indeksy[i] = i;
        }

        sortuj(wartoscDoWagi, indeksy, n);

        int wynik = 0;

        for (int i = 0; i < n; i++) {
            int indeks = indeksy[i];
            if (wagi[indeks] <= pojemnosc) {
                pojemnosc -= wagi[indeks];
                wynik += wartosci[indeks];
                System.out.println("Spakowano przedmiot " + nazwy[indeks] + " (indeks " + indeks + ")");
            }
        }

        System.out.println("\nWartosc spakowanych przedmiotow: " + wynik);
    }

    public static void main(String[] args) {
        String[] nazwy = {"aparat", "baterie", "czajnik", "dmuchany materac", "ekologiczny prysznic", "filtr", "garnuszek"};
        int[] wartosci = {4, 15, 6, 13, 5, 12, 3};
        int[] wagi = {8, 3, 2, 6, 15, 16, 2};
        int n = 7;
        int pojemnosc = 21;

        decyzyjnyPlecak(nazwy, wartosci, wagi, n, pojemnosc);
    }
}

Wynik działania programu

Spakowano przedmiot baterie (indeks 1)
Spakowano przedmiot czajnik (indeks 2)
Spakowano przedmiot dmuchany materac (indeks 3)
Spakowano przedmiot garnuszek (indeks 6)
Spakowano przedmiot aparat (indeks 0)

Wartosc spakowanych przedmiotow: 41

Słownik

algorytm zachłanny

algorytm wybierający na każdym kroku lokalnie najlepsze rozwiązanie, licząc, że doprowadzi to do globalnie optymalnegooptymalizacjaoptymalnego rozwiązania problemu

optymalizacja

(od łac. optimus – najlepszy) poprawa wydajności algorytmu uzyskana dzięki zmniejszeniu liczby operacji niezbędnych do otrzymania wyniku

Wprowadzenie

Prezentacja multimedialna

Implementacja rozwiązań różnych wariantów problemu plecakowego w języku Java

Ogólny problem plecakowy

Decyzyjny problem plecakowy

Słownik