knapsack

/*
0/1 Knapsack problem
B(i, m) -- the maximum profit of choose i with capacity m
  = max{  B(i-1, m)    if wi >m
		B(i-1, m-wi)+bi  if wi<=m
		}
And B(0,m) = 0, B(i,0) = 0
*/
public class Knapsack{

public static void main(String[] args){
	int M = 5;
	int max_profit = knapsack1(weight.length, M);
	System.out.println(max_profit);
}
// compute in bottom up manner
private static int knapsack(int n, int M){
	int[][] B = new int[n+1][M+1];
	for (int i=0; i<n+1; i++)
		B[i][0] = 0;

	for (int i=0; i<M+1; i++)
		B[0][i] = 0;

	for (int i=1; i<n+1; i++)
		for (int j=1; j<M+1; j++){
			if (weight[i-1]<=j)
				B[i][j] = Math.max(B[i-1][j-weight[i-1]] + profit[i-1], B[i-1][j]);
			else
				B[i][j] = B[i-1][j];
	}
	for (int i=0; i<n+1; i++){
		for (int j=0; j<M+1; j++)
			System.out.print(B[i][j]+" ");
		System.out.println();
	}
	return B[n][M];
}

// compute in recursive manner
private static int knapsack1(int n, int M){
	int max_profit;
	if (M<=0 || n ==0)
		return 0;
	else{
		if (M>=weight[n-1])
			max_profit = Math.max(knapsack1(n-1, M-weight[n-1])+profit[n-1], knapsack1(n-1, M));
		else
			max_profit = knapsack1(n-1, M);
	}
	return max_profit;
	}

private static int[] weight = {2,3,4,5};
private static int[] profit = {3,4,5,6};

}