Knapsack Problem:

Knapsack.java , KnapsackDriver.java.

Knapsack problem that uses brute force, Dynamic programing, and greedy approximation algorithms to solve the knapsack problem.

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

Public class Knapsack{

//private fields

Public knapsack(int W, int [] w, int[] b)

{

//constructor

}

}

Public static int[] generateSubset(int k, int n)

{

//0<= k <=2ⁿ - 1

//generates the kth subset of {0,n-1} and the kth subset is the binary representation of k using n bits

}

public void BruteForceSolution() {

//generates and prints all optimal solutions of the knp problem.

// uses the generateSubset method to generate all subsets of the input items

}

public void DynamicProgrammingSolution(boolean printBmatrix) {

//generates and prints one optimal solution for the knp problem.

// must use recurrence 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, w w_k] + b_k }

//2D matrix B must be created using O(n²) algorithm to fill the array

// program must use the matrix to find the optimal set of items and benefit to be added to the knapsack.

//print the OPT matrix when requested

}

public void GreedyApproximateSolution()

{

// print an approximate solution for 0-1 knp

//add whole items to the knapsack in decreasing benefit/weight ratio order.

}

Test case:

Test Case #1 Knapsack Problem Instance Number of items = 7Knapsack Capacity = 100 Input weights:[-1, 60, 50, 60, 50, 70, 70, 45] Input benefits:[-1, 180, 95, 40, 95, 40, 40, 105] Brute Force Solutions Optimal Set= { 4,7 } weight sum = 95benefit sum = 200 Optimal Set= { 2,7 } weight sum = 95benefit sum = 200 Dynamic Programming Solution Optimal Set= { 2,7 } weight sum = 95benefit sum = 200 Greedy Approximate Solution Optimal Set= { 1 }weight sum = 60benefit sum = 180