fork(4) download
copy 
  1. /* package whatever; // don't place package name! */
  2.  
  3. import java.util.*;
  4. import java.lang.*;
  5. import java.io.*;
  6.  
  7. /* Name of the class has to be "Main" only if the class is public. */
  8. class Ideone
  9. {
  10. 	public static void main (String[] args) throws java.lang.Exception
  11. 	{
  12. 		    int val[] = {60, 100, 120};
  13.     int wt[] = {10, 20, 30};
  14.     int  W = 50;
  15.  
  16.         solution(val,wt,W);
  17. 	}
  18. 	public static void solution(int[] val,int[] wt,int W)
  19.      {
  20.     System.out.println("Recursive naive approach = "+Naive_recursive(val,wt,W,0));
  21.     System.out.println("DP bottom Up = "+dp_bottomUp(W,wt,val));
  22.      }
  23.  
  24.  
  25.      // want to maximize the subset value of val for W=0
  26.      public static int Naive_recursive(int[] val,int[] wt,int W,int i)
  27.      {
  28.          // variable i indicate particular value to be included or not
  29.          if(W==0 || i>wt.length-1) 
  30.          {
  31.                 return 0;
  32.          }         
  33.  
  34.       if(wt[i]>W)   
  35.           return Naive_recursive(val,wt,W,i+1);
  36.       else   
  37.      return Math.max(val[i]+Naive_recursive(val,wt,W-wt[i],i+1),Naive_recursive(val,wt,W,i+1));
  38.  
  39.      }
  40.  
  41.  
  42.     public static int dp_bottomUp(int W, int wt[], int val[])
  43.     {
  44.         // table formation
  45.       //  System.out.println("len = "+(val.length+1));
  46.  
  47.         int[][] t=new int[val.length+1][W+1];
  48.         int i,j;
  49.  
  50.         for(i=0;i<=val.length;i++)
  51.             t[i][0]=0;
  52.  
  53.         for(j=0;j<=W;j++)
  54.             t[0][j]=0;
  55.  
  56.         for(i=1;i<=val.length;i++)
  57.         {
  58.             for(j=1;j<=W;j++)
  59.             {
  60.                 //System.out.println("i= "+i+" j= "+j);
  61.                     if(wt[i-1]<=j)
  62.                     {
  63.                         t[i][j]=Math.max(val[i-1]+t[i-1][j-wt[i-1]],t[i-1][j]);
  64.                     }
  65.                     else
  66.                     {
  67.                         t[i][j]=t[i-1][j];
  68.                     }
  69.             }
  70.         }
  71.  
  72.         return t[--i][--j];
  73.  
  74.     }
  75. }
Success #stdin #stdout 0.07s 380224KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Recursive naive approach = 220
DP bottom Up = 220
https://ideone.com/mFaz8X
language:
Java (HotSpot 12)
created:
10 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!