class Ideone{
 
	public static void main(String[] args){
		int val[] = {15, 9, 5, 10};
		int wt[] = {1, 3, 4, 5};
		int  maxWeight = 8;
		System.out.println("Max value obtained from knapsack => "+ maxKnapSackValue(val, wt, maxWeight, val.length));
		System.out.println("Max value obtained form dp knapsack => "+ knapsackDPSolution(val, wt, maxWeight));
	}
 
	private static int knapsackDPSolution(int[] val, int[] wt, int maxWeight){
		int[][] dp = new int[val.length+1][maxWeight+1];	
		for(int i=0; i<=wt.length; i++){
			for(int w=0; w<=maxWeight; w++){
				if(i==0 || w==0){
					dp[i][w] = 0;
				}else if(wt[i-1] <= w){
					dp[i][w] = max(val[i-1]+dp[i-1][w-wt[i-1]], dp[i-1][w]);
				}else{
					dp[i][w] = dp[i-1][w];
				}
			}
		}
		return dp[wt.length][maxWeight];
	}
 
	//Recursive solution
	private static int maxKnapSackValue(int[] val, int[] wt, int maxWeight, int n){
		if(n==0 || maxWeight == 0 ) return 0;
 
		//If weight of nth item is more than max capacity, it cannot be inclded
		if(wt[n-1] > maxWeight) return maxKnapSackValue(val, wt, maxWeight, n-1);
		else return max(val[n-1] + maxKnapSackValue(val, wt, maxWeight-wt[n-1], n-1), maxKnapSackValue(val, wt, maxWeight, n-1));
	}
 
	private static int max(int a, int b){
		return a>b?a:b;
	}
}