Question

JAVA question.

Pages 305 and 306 of your text discusses the Knapsack Problem. Write a program that solves the Knapsack problem. Code to the following standards.

Your source of items to put into the knapsack should consist of five randomly generated integers in the range of 1 to 20.

Your knapsack can hold 20 lbs.

Knapsack code traditionally ends when you find a total weight of items that equals the capacity of the knapsack. In this case, it is possible that you will never reach the knapsack capacity. It is also possible that a single item will be big enough to fill the backpack. Make sure your code ends gracefully if that occurs.

WARNING: I often get solutions to this exercise that do not use recursion. If you submit one of those, it's an automatic zero. Understand what recursion is before you submit your exercise.

Answer 1

import java.util.Random;

public class KnapsackProblem {
  
public static void main(String[] args)
{
int values[] = new int[5]; // array to store 5 random numbers
int weights[] = new int[5]; // array to store their weights: generate 5 random weights between 1-10
int knapSackCapacity = 20; // maximum capacity of the knapsack
int maxWeight = 0;
  
do
{
// generate 5 random numbers betweeb 1-20 and insert them into array "values"
for(int i = 0; i < 5; i++)
{
Random random = new Random();
int pick = 1 + random.nextInt(20 - 1);
while(pick < 1 || pick > 20)
{
pick = 1 + random.nextInt(20 - 1);
}
values[i] = pick;
}

// generate 5 random weights between 1-20 and insert them into array "weights"
for(int i = 0; i < 5; i++)
{
Random random = new Random();
int pick = 1 + random.nextInt(20 - 1);
while(pick < 1 || pick > 20)
{
pick = 1 + random.nextInt(20 - 1);
}
weights[i] = pick;
}

int n = values.length; // number of items in the array

maxWeight = recursiveKnapSackSolution(knapSackCapacity, weights, values, n);
if(maxWeight <= knapSackCapacity)
break;
}while(maxWeight > knapSackCapacity);
  
System.out.print("Values: [ ");
for(int i = 0; i < 5; i++)
{
if(i == 4)
System.out.println(values[i] + " ]");
else
System.out.print(values[i] + ", ");
}
  
System.out.print("Weights: [ ");
for(int i = 0; i < 5; i++)
{
if(i == 4)
System.out.println(weights[i] + " ]");
else
System.out.print(weights[i] + ", ");
}
  
System.out.println("The total maximum permissible values sum up to: " + maxWeight);
}
  
private static int getMaximumValue(int num1, int num2)
{
return(num1 > num2) ? num1 : num2;
}
  
private static int recursiveKnapSackSolution(int capacity, int weights[], int values[], int numberOfWeights)
{
// base case
if(numberOfWeights == 0 || capacity == 0)
return 0;
  
// pre-condition: if weight of n-th item is greater than capacity, ignore it
// else get the maximum of the following 2 cases: n-th item included and n-th item not included
if(weights[numberOfWeights - 1] > capacity)
return recursiveKnapSackSolution(capacity, weights, values, numberOfWeights - 1);
else
{
  
return getMaximumValue(
values[numberOfWeights - 1]
+ recursiveKnapSackSolution(capacity - weights[numberOfWeights - 1], weights, values, numberOfWeights - 1),
recursiveKnapSackSolution(capacity, weights, values, numberOfWeights - 1));
}
}
}

******************************************************************* SCREENSHOT ********************************************************