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 <=2n - 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 < wk then B[k,w] = B[k-1,w].Otherwise, B[k,w] = max { B[k-1,w] , B[k, w wk] + bk } //2D matrix B must be created using O(n2) 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