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]}