Question

You want to put your valuable items into a box. The maximum capacity of the box is 4. The table below shows the values and weights for items 1, 2, 3 and 4 respectively.

Item i	Value Vi	Weight Wi
1	15	1
2	10	5
3	9	3
4	5	2

        (i) Use recursion strategy to put the items into the box such that it holds the highest value

        (ii) Repeat (i) above using backtracking approach.

Answer 1

class Knapsack {

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

int val[] = {10, 40, 30, 50};

int wt[] = {5, 4, 6, 3};

int W = 10;

System.out.println(knapsack(val, wt, W));

}

public static int knapsack(int val[], int wt[], int W) {

//Get the total number of items.

//Could be wt.length or val.length. Doesn't matter

int N = wt.length;

//Create a matrix.

//Items are in rows and weight at in columns +1 on each side

int[][] V = new int[N + 1][W + 1];

//What if the knapsack's capacity is 0 - Set

//all columns at row 0 to be 0

for (int col = 0; col <= W; col++) {

V[0][col] = 0;

}

//What if there are no items at home.

//Fill the first row with 0
for (int row = 0; row <= N; row++) {

V[row][0] = 0;
}

for (int item=1;item<=N;item++){

//Let's fill the values row by row

for (int weight=1;weight<=W;weight++){

//Is the current items weight less

//than or equal to running weight

if (wt[item-1]<=weight){

//Given a weight, check if the value of the current

//item + value of the item that we could afford

//with the remaining weight is greater than the value

//without the current item itself

V[item][weight]=Math.max (val[item-1]+V[item-1][weight-wt[item-1]], V[item-1][weight]);
}

else {

//If the current item's weight is more than the

//running weight, just carry forward the value

//without the current item

V[item][weight]=V[item-1][weight];
}
}

}

//Printing the matrix

for (int[] rows : V) {

for (int col : rows) {

System.out.format("%5d", col);
}
System.out.println();
}

return V[N][W];

}

}

It is in java