Question

I'm having trouble with my Java Homework in which my professor wants us to solve the 0-1 Knapsack problem with Dynamic Programming. The code below is what she provided and she requested that we not change any of her existing code but simply add to it. As you can see she gave us the stub file for the knapsack class and the Item class.

You are a thief with a knapsack with a carrying capacity of knapsackCapacity pounds. You want to stuff as much value into the knapsack as possible.

There are numberOfItems of items you can pick, weights between minWeight to maxWeight and valued from minValue to maxValue. What is the list of items you will stuff into your knapsack and what is the total value?

import java.util.*;

public class Knapsack {

public static void main(String[] args) {
final int numberOfItems = 10;
final int minWeight = 1;
final int maxWeight = 5;
final int minValue = 50;
final int maxValue = 100;
final int knapsackCapacity = 20;
Item[] items = genItems(numberOfItems, minValue, maxValue, minWeight, maxWeight);

// your work here

}

static Item[] genItems(int howMany, int lValue, int hValue, int lWeight, int hWeight) {
Item[] results = new Item[howMany];
for (int i = 0; i < howMany; i++) {
int value = (int) (Math.random() * (hValue - lValue + 1)) + lValue;
int weight = (int) (Math.random() * (hWeight - lWeight + 1)) + lWeight;
results[i] = new Item("Item" + i, value, weight);
}
return results;
}

}

// My Item Class

public class Item {
String name;
int value;
int weight;

public Item(String s, int v, int w) {
name = s;
value = v;
weight = w;
}

@Override
public String toString() {
return name + ":" + value + "|" + weight;
}
}

Answer 1

Item.java

public class Item {

String name;
int value;
int weight;

public Item(String s, int v, int w) {
name = s;
value = v;
weight = w;
}

@Override
public String toString() {
return name + ": " + value + " | " + weight;
}
}

Knapsack.java (Main class)

public class Knapsack {
  
public static void main(String[] args)
{
final int numberOfItems = 10;
final int minWeight = 1;
final int maxWeight = 5;
final int minValue = 50;
final int maxValue = 100;
final int knapsackCapacity = 50;
Item[] items = genItems(numberOfItems, minValue, maxValue, minWeight, maxWeight);

knapSack(knapsackCapacity, items, numberOfItems);

}

private static Item[] genItems(int howMany, int lValue, int hValue, int lWeight, int hWeight)
{
Item[] results = new Item[howMany];
for (int i = 0; i < howMany; i++)
{
int value = (int) (Math.random() * (hValue - lValue + 1)) + lValue;
int weight = (int) (Math.random() * (hWeight - lWeight + 1)) + lWeight;
results[i] = new Item("Item" + i, value, weight);
}
return results;
}
  
private static int getMax(int a, int b) { return (a > b)? a : b; }
  
private static void knapSack(int knapsackCapacity, Item items[], int numberOfItems)
{
int i, w;
int knapSack[][] = new int[numberOfItems + 1][knapsackCapacity + 1];
for(i = 0; i <= numberOfItems; i++)
{
for(w = 0; w <= knapsackCapacity; w++)
{
if(i ==0 || w == 0)
knapSack[i][w] = 0;
else if(items[i - 1].weight <= w)
knapSack[i][w] = getMax(items[i - 1].value + knapSack[i - 1][w - items[i - 1].weight], knapSack[i - 1][w]);
else
knapSack[i][w] = knapSack[i - 1][w];
}
}
  
// store the result of Knapsack
int result = knapSack[numberOfItems][knapsackCapacity];
System.out.println("Total value: " + result + "\n");
  
w = knapsackCapacity;
for(i = numberOfItems; i > 0 && result > 0; i--)
{
// either the result comes from the top
// (knapSack[i - 1][w]) or from (items[i - 1].value + K[i-1][w - items[i - 1].weight]).
// If it comes from the latter one it means the item is included in the Knapsack.
if (result == knapSack[i - 1][w])
continue;
else
{
// this item is included and so print it
System.out.println(items[i - 1].toString());
  
// As this weight is included in the Knapsack, it's value is deducted from the Knapsack table.
result = result - items[i - 1].value;
w = w - items[i - 1].weight;
}
}
}
}

******************************************************************** SCREENSHOTS *****************************************************

SAMPLE OUTPUT 1:

CD run: Total value: 817 Item9 78 2 Item8 64 | 4 Item7 93 | 3 Item6: 75 1 Item5 96 I 4 Item4: 65 3 Item3: 63 4 Item2: 93 I 4 Iteml: 99 3 Itemo: 91 1 BUILD SUCCESSFUL (total time: 0 seconds)

SAMPLE OUTPUT 2:

DD run: Total value: 805 Item9 81 4 Item8 94 5 Item7 76 3 Item6: 60 5 Item5 82 3 Item4 97 | 2 Item3: 81 | 4 Item2: 74 | 5 Iteml 84 5 Item0: 76 I 3 BUILD SUCCESSFUL (total time: 0 seconds)

SAMPLE OUTPUT 3:

run: DD Total value: 689 Item9 54 3 Item8 65 5 Item7 50 I 5 Item6: 74 3 Item5 88 I 2 Item4 68 I 1 Item3 55 4 Item2: 97 1 Iteml: 56 3 Itemo: 82 1 BUILD SUCCESSFUL (total time: 0 seconds)

**********************************************************************************************************************************************