Informatiker Board | Druckvorschau: Rucksackproblem mit Wert, Gewicht & Volumen

Informatiker Board (http://www.informatikerboard.de/board/index.php)
- Themengebiete (http://www.informatikerboard.de/board/board.php?boardid=1)
--- Praktische Informatik (http://www.informatikerboard.de/board/board.php?boardid=6)
---- Algorithmen (http://www.informatikerboard.de/board/board.php?boardid=17)
----- Rucksackproblem mit Wert, Gewicht & Volumen (http://www.informatikerboard.de/board/thread.php?threadid=1564)

Geschrieben von blume257 am 26.07.2013 um 20:38:

Rucksackproblem mit Wert, Gewicht & Volumen

Meine Frage:
Guten Abend ihr Lieben,

ich schreibe bald eine Klausur und habe noch ein einziges Problem bei dem ich einfach nicht weiter weiß... unglücklich

Vielleicht kann mir einer von euch helfen?! Es geht um das Rucksackproblem, allerdings mit Wert, Volumen & Gewicht. Ich soll die Aufgabe im Pseudocode schreiben, habe es allerdings erst mal zu kompilieren versucht... folgender Code ist meiner:

code:

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:

public static int[][] algo(int[] volumen, int[] gewicht, int [] wert,int volKapa, int gewKapa){
        
        
        int[][] c = new int[wert.length+1 ][gewKapa+1];
        for(int i=0;i<gewKapa;i++){
            c[i][0]=0;
        }
        
        
        for(int i=1;i<=wert.length;i++){
            for(int j=1;j<=gewKapa;j++){
                
                if(j<gewicht[i]    ||  j< volumen[i] {
                    c[i][j] =c[i-1][j];
                }
                else{
                    
                    c[i][j] =Math.max(c[i-1][j], wert[i-1]+c[i-1][j-gewicht[i-1]]);
                }
            }
        }
        return c;
    }

Allerdings funktioniert es einfach nicht für alle Eingaben und ich sitze schon einige Zeit daran, weiß nicht mehr weiter hab den Code schon gefühlte tausende Male geändert. Weiß jemand vielleicht meinen Fehler oder kennt einen guten Pseudocode? Ich wäre zu ewigem Dank verpflichtet!!

Liebe Grüße,
blume257

Meine Ideen:

code:

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:

public static int[][] algo(int[] volumen, int[] gewicht, int [] wert,int volKapa, int gewKapa){
        
        
        int[][] c = new int[wert.length+1 ][gewKapa+1];
        for(int i=0;i<gewKapa;i++){
            c[i][0]=0;
        }
        
        
        for(int i=1;i<=wert.length;i++){
            for(int j=1;j<=gewKapa;j++){
                
                if(j<gewicht[i]    ||  j< volumen[i] {
                    c[i][j] =c[i-1][j];
                }
                else{
                    
                    c[i][j] =Math.max(c[i-1][j], wert[i-1]+c[i-1][j-gewicht[i-1]]);
                }
            }
        }
        return c;
    }

Geschrieben von eulerscheZahl am 26.07.2013 um 21:13:

Sollte funktionieren, ist aber eine reine Brute-Force Lösung:

code:

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:

public class main {
	public static boolean[] algo(int[] volumen, int[] gewicht, int [] wert,int volKapa, int gewKapa){
		int optWert=0; //hier wird immer die höchste bisher einzielte Summe gespeichert
		int ergebnis = 0;
		
		for(int i = 0; i<Math.pow(2, wert.length); i++){
			//Binärdarstellung der Zahl, um zu entscheiden, welche Kisten eingepackt werden
			//stattdessen wäre auch Rekursion denkbar (und vor allem bei geringer Kapazität schneller, da bei einem vollen Rucksack abgebrochen werden kann)
			int momGewicht = 0;
			int momVolumen = 0;
			int momWert = 0;
			for(int kiste = 0; kiste < wert.length; kiste++){
				if (((i >> kiste) & 1) == 1){
					momGewicht += gewicht[kiste];
					momVolumen += volumen[kiste];
					momWert += wert[kiste];
				}
			}
			if(momVolumen <= volKapa && momGewicht <= gewKapa && optWert < momWert){
				optWert = momWert;
				ergebnis = i;
			}
		}
		boolean[] einpacken = new boolean[wert.length];
		for(int kiste = 0; kiste < wert.length; kiste++){
			if (((ergebnis >> kiste) & 1) == 1){
				einpacken[kiste] = true;
			}
		}
		return einpacken;		
	}
	
	public static void main(String[] args)
	{
		int[] volumen = {1,2,3,4,5,6,7,8,9};
		int[] gewicht = {3,4,9,7,1,2,6,8,5};
		int[] wert = {1,2,3,4,5,6,7,8,9};
		boolean[] einpacken = algo(volumen, gewicht, wert, 30,30);
		for(boolean i:einpacken)
			System.out.println(i);
	}
}

Geschrieben von eulerscheZahl am 29.07.2013 um 09:11:

Wo wir neulich dabei waren, was uns aufragt: das regt mich auf böse

Da steht "bald" im Text, woraus man ein dringend ableiten könnte, das Rucksackproblem ist noch nicht einmal erklärt, weswegen man erst selbst suchen muss, worum es sich dabei handelt. Trotzdem habe ich nach gerade einmal 35 Minuten mit einem lauffähigen Programm geantwortet - und nachdem mir vorher "ewiger Dank" versprochen wurde, kommt: nichts!
Und ich weiß auch, warum: der Fragesteller hat hier vermutlich gar nicht mehr reingeschaut, sondern stattdessen an anderer Stelle nach Rat gesucht, das informatikerboard war nur 4. Wahl (und trotzdem wurde hier als erstes geantwortet).

In google nach doppelten Einträgen zu suchen, bringt meist nichts, da dort nicht oft genug gecrawlt wird und ich kann ja auch nicht alle mir bekannten Informatikforen absuchen, bevor ich mich bequeme, zu antworten, weshalb mir das sicher noch öfter passieren wird.
Aber das ist einfach nur unverschämt!

Edit:
Airblader ist dem auch zum Opfer gefallen.