DP Problema rucsacului

knapsack.java

import java.io.*;
import java.util.*;

public class Rucsac {


       public static void main(String[] args) throws IOException {

              BufferedReader fin = new BufferedReader(new FileReader("rucsac.in"));

              PrintWriter fout = new PrintWriter(new FileWriter("rucsac.out"));

              StringTokenizer st = new StringTokenizer(fin.readLine());

              int n =  Integer.parseInt(st.nextToken());
              int G = Integer.parseInt(st.nextToken());

              int[] g = new int[n+1];
              int[] p = new int[n+1];


              for(int i = 1; i <= n; ++i) {

              	    st = new StringTokenizer(fin.readLine());

              	    g[i] = Integer.parseInt(st.nextToken());

              	    p[i] = Integer.parseInt(st.nextToken());              	    

              }
              

              //Contruim Table DP 

       	      int[][] DP = new int[n+1][G + 1];


       	      for(int i = 1; i <= n; ++i) {

                    for(int j = 0; j <= G; j++) {

                    	 if(g[i] > j) { //daca nu incape in rucsacul de capacitate j
 
                            DP[i][j] = DP[i-1][j];

                    	 } else {
                             //aleg obiectul 
                    	 	 DP[i][j] = Math.max(DP[i-1][j], DP[i-1][j- g[i]] + p[i]);
                    	 }
                    }
       	      }  


       	      fout.println("Table Castig (DP):\n");
              
       	      fout.write("    ");

       	      for(int j = 0; j <= G; ++j) 

       	      	  fout.printf("%3d", j);

       	      fout.println();

              for(int i = 0; i <= n; ++i) {

       	          fout.printf("i=%d ", i); 

       	          for(int j = 0; j <= G; j++) {

       	          	 fout.printf("%3d", DP[i][j]);
       	          }

       	          fout.println();
       	      }

            
              //profit maxim
       	      fout.println("Profit maxim: " + DP[n][G]);
       	      //System.out.println(DP[n][G]);


       	      //reconstruire solutie
       	      int j = G;

       	      List<Integer> obiecte = new ArrayList<>();

       	      for(int i = n; i >= 1; --i) {

       	      	  if(DP[i][j] != DP[i-1][j]) {

       	      	  	  obiecte.add(i);
       	      	  	  j -= g[i];
       	      	  }
       	      }

       	      fout.print("Obiecte alese: ");

       	      for(int i = obiecte.size() - 1; i >= 0; i--) {

       	      	fout.print(obiecte.get(i) + " ");
       	      }

       	      fout.println();

              fin.close();
       	      fout.close();

       }

}