Java knapsack Dynamic programming:

Testcase #1 int n = 7; int[] weights = {-1, 60, 50, 60, 50, 70, 70, 45}; int W = 100; int[] benefits = {-1, 180, 95, 40, 95, 40, 40, 105};

Input:

int n //number of items //index items from 1 to n

int[] w // w[i] = weight of item i //Set w[0] = -1

int[] b // b[i] = benefit of item i //Set b[0] = -1

int W //weight capacity of the knapsack

output:

1. Optimal set of items to put into the knapsack

2. Total weight of the items in knapsack. Total benefit of the items in knapsack

Create method using the recursive equation:

B[0,w] = 0for0 <= w <= W

for k > 0,

if w < w_k then B[k,w] = B[k-1,w].Otherwise,

B[k,w] = max { B[k-1,w] , B[k-1, w w_k] + b_k }

Knapsack.java

public class Knapsack { //set privates public Knapsack(int W, int[] w, int[] b) { //constructor }

public void DynamicProgrammingSolution(boolean printBmatrix) { //Prints one solutions knapsack problem // use dynamic programming algorithm // Print solution in format specified in Project 2 // If printmatrix is true, print the OPT matrix. }

}

KnapsackDriver.java

public class KnapsackDriver3 { public static void main( String[] args) { int n = 7; int[] weights = {-1, 60, 50, 60, 50, 70, 70, 45}; int W = 100; int[] benefits = {-1, 180, 95, 40, 95, 40, 40, 105};

System.out.println(" Dynamic Programming Solution"); Knapsack kp = new Knapsack(W,weights, benefits); kp.DynamicProgrammingSolution(false);

}