KnapSack01

/*
 * To change this license header, choose License Headers in Project Properties.
 * To change this template file, choose Tools | Templates
 * and open the template in the editor.
 */
package javaapplication37;

/**
 *
 * @author Asif
 */
public class JavaApplication37 {

    /**
     * @param args the command line arguments
     */

    static int max(int a,int b) {
        if(a>b) {
            return a;
        } else {
            return  b;
        }
    }
   static void kanp(int w[],int p[],int k) {
       int kk[][] = new int[w.length][k+1];
       Item ar[][] = new Item[w.length][k+1];
       for(int i=1;i<p.length;i++) {
           for(int j=1;j<=k;j++) {
               if(w[i]<=j) {
                   //System.out.println("jj");
                   int x = p[i]+ kk[i-1][j-w[i]];
                   int y = kk[i-1][j];
                   int max = max(x,y);
                   kk[i][j]= max;
                   if(max ==x) {
                       ar[i][j] = new Item(i-1, j-w[i], "leftup");
                   }else {
                       ar[i][j] = new Item(i-1, j, "left");
                   }
               } else {
                   kk[i][j] = kk[i-1][j];
                   ar[i][j] = new Item(i-1, j, "left");
               }
           }
         //  System.out.println("");
       }
       for(int i=0;i<p.length;i++) {
           for(int j=0;j<=k;j++) {
               System.out.print(kk[i][j]+" ");
           }
         System.out.println("");
       }

      int i = w.length-1;
      int j = k;
      Item x = ar[i][j];
      while(x != null) {
          if(x.getX().equals("leftup")) {
              System.out.println(i);
              i = x.getI();
              j = x.getJ();
              x = ar[i][j];
          }else {
              i = x.getI();
              j = x.getJ();
              x = ar[i][j];

          }
      }

   }
    public static void main(String[] args) {
        int w[] = {0,2,1,3,2};
        int p[] = {0,12,10,20,15};
        int k = 5;
        kanp(w, p, k);

       // System.out.println(w.length);

    }

}

class Item {
    int i,j;
    String x;

    public Item(int i, int j, String x) {
        this.i = i;
        this.j = j;
        this.x = x;
    }

    public int getI() {
        return i;
    }

    public int getJ() {
        return j;
    }

    public String getX() {
        return x;
    }

}