Beiträge

Beginner   Java allgemein   JDBC   JNI   Networking   Online-Ressourcen   Swing + AWT   XML   Meckerecke    Antworten     Neuer Beitrag     Gesamtdarstellung Detaildarstellung Einzeldarstellung Threaddarstellung

Beitrag 275 von 2963 (9%)

Autor	ballibum
Datum	23.08.08, 14:00
Betreff	RUcksackproblem

---

hallo liebe foren nutzer,
ich teste gerade das altbekannte rucksackproblem, die rekursive lösung habe ich schon bewältigen können , doch nun hänge ich bei der dynamischen programmierung fest. leider spuckt mir der quellcode so absolut nicht den optimal wert aus. ich würde euch bitten einen blick auf meinen code zu werfen.
package dprucksack;

public class dprucksack {
    
    static int gewichte[]={2,2,6,5,4};
    static int wertigkeit[]={6,3,5,4,6};
    static int kapazitaet = 10;
    public static int entscheidung(int mit, int ohne) {
        if (mit > ohne){
            return mit;
        }
        else{
            return ohne;
        }
    }
    public static void main(String[] args) {
        int x;
        int startwert;
        startwert = 0;
        System.out.println(kapazitaet+1);
        System.out.println(wertigkeit.length-1);
        x= rucksack(startwert,kapazitaet);
        System.out.println("Die optimale Wertigkeit liegt bei:"+x);
        
    }
    public static int rucksack(int n, int kapazitaet){
        int [][] feld = new int [wertigkeit.length][kapazitaet+1]; for (int r=0; r<= kapazitaet; r=r+1)
        if (gewichte[n]>r)
        feld[n][r]=0;
        else
        feld[n][r]=wertigkeit[n];
        for (int i=n-1; i>=2; i=i-1)
        for (int r=0;r<=kapazitaet; r=r+1)
        if(gewichte[i]>r)
        feld[i][r]=feld[i+1][r];
        else
        feld[i][r]=entscheidung(feld[i+1][r],feld[i+1][r-gewichte[i]]+wertigkeit[i]);
        if (gewichte[0]>kapazitaet)
        [color=red] return feld[1][kapazitaet];
        else
        return entscheidung(feld[1][kapazitaet],feld[1][kapazitaet-gewichte[0]]+wertigkeit[0]);
    }[/color]
}

ich denke meine fehler befinden sich in den rot markierteb bereichen.
ich wäre euch sehr dankbar , wenn ihr mir helfen könntet, es reicht mir aus das ich das optimum ausgegeben bekomme, den rest möchte ich eigenständig weiter machen mfg tim

---

Auf diesen Beitrag antworten   Neuen Beitrag verfassen