Algorytm plecakowy zachłanny

0

Witam,
mam taki oto programik, który oblicza stosunek wartości do objętości przedmiotu i wkłada go do plecaczka. Tylko gdzieś pojawił się jakiś błąd w sztuce bo objętość plecaczka wynosi "10" a przedmioty które wkłada program mają objętość "12". Czy mógłby mnie ktoś nakierować co jest tu źle, byłbym bardzo wdzięczny. Dziękuję.

package plecakzachlanny;

public class PlecakZachlannyS {

    final static int N = 6;                // liczba przedmiotów
    final static int MAX_V = 10;           // objetość plecaka
    final static int[] V = {6, 2, 3, 2, 3, 1}; //objetosci przedmiotow
    final static int[] W = {6, 4, 5, 7, 10, 2}; //wartosci przedmiotow

    //Wersja wybierania w kolejnosci roznacych objetosci przedmiotów
    public static void pakujPoWartosciIObjetosci() {
        boolean[] rozw = new boolean[N]; //tablica na optymalny podzbior
        int sumW = 0;
        int sumV = 0;
       
        while (true) {
            int maxW = 0;
            int i;
            int ilo = 1;
            int maxPoz = -1;
            for (i = 0; i < N; i++) { //Szukamy najmniejszego przedmiotu, ktory jeszcze nie zostal zabrany
                ilo = W[i]/V[i];
                if (!rozw[i]) { //jesli jeszcze nie zabrany
                    if ((sumV + ilo <= MAX_V) && (ilo > maxW)) {
                        maxW = V[i];
                        maxPoz = i;
                    }
                }
            }

            if (maxPoz > -1) {
                rozw[maxPoz] = true;
                sumW = sumW + W[maxPoz];
                sumV = sumV + V[maxPoz];
            } else {
                break;
            }

        }
        System.out.println("Objetosc plecaczka: "+MAX_V);
        System.out.println("Wartosc po zapakowaniu plecaka: " + sumW);
        System.out.println("Objetosc po zapakowaniu plecaka: " + sumV);
        System.out.print("Przedmioty w plecaku: ");

        for (int i = 0; i < N; i++) {
            if (rozw[i]) {
                System.out.print(i + " ");
            }
        }
        System.out.println();

    }

    public static void main(String[] args) {

        System.out.println("Pakuj: ");
        pakujPoWartosciIObjetosci();
    }
}

0
  1. (sumV+V[i]<=MAX_V)
  2. double maxW=0;
  3. double ilo;
  4. ilo=(double)W[i]/V[i];
0

Dzięki :*

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