Source of Knapsack01Demo.java

Structures and functions

class Item
class ItemValueComparator implements Comparator
class Knapsack
public class Knapsack01Demo

  1: //Knapsack01.java

  3: import java.util.ArrayList;
  4: import java.util.Arrays;
  5: import java.util.Comparator;
  6: import java.util.Scanner;

  8: class Item
  9: {
 10:     public double weight;
 11:     public double value;

 13:     Item
 14:     (
 15:         double itemWeight,
 16:         double itemValue
 17:     )
 18:     {
 19:         weight = itemWeight;
 20:         value = itemValue;
 21:     }
 22: }

 24: class ItemValueComparator implements Comparator<Item>
 25: {
 26:     public int compare
 27:     (
 28:         Item item1,
 29:         Item item2
 30:     )
 31:     {
 32:         if (item1.value < item2.value)
 33:         {
 34:             return 1;
 35:         }
 36:         else if (item1.value > item2.value)
 37:         {
 38:             return -1;
 39:         }
 40:         return 0;
 41:     }
 42: }

 44: class Knapsack
 45: {
 46:     private double maxWeight;
 47:     private ArrayList<Item> items;

 49:     Knapsack(double maximumWeight)
 50:     {
 51:         maxWeight = maximumWeight;
 52:         items = new ArrayList<Item>();
 53:     }

 55:     public ArrayList<Item> getItems()
 56:     {
 57:         return this.items;
 58:     }

 60:     public double getMaxWeight()
 61:     {
 62:         return maxWeight;
 63:     }

 65:     public static Knapsack knapsack01
 66:     (
 67:         Item[] availableItems,
 68:         double maxWeight
 69:     )
 70:     {
 71:         // Sort the items in descending order based on value
 72:         Arrays.sort(availableItems, new ItemValueComparator());

 74:         // Initialize a new knapsack to hold items
 75:         Knapsack knapsack = new Knapsack(maxWeight);

 77:         double remaining = maxWeight;
 78:         for (Item item : availableItems)
 79:         {
 80:             if (item.weight <= remaining)
 81:             {
 82:                 knapsack.getItems().add(item);
 83:                 remaining -= item.weight;
 84:             }
 85:         }

 87:         return knapsack;
 88:     }
 89: }

 91: public class Knapsack01Demo
 92: {
 93:     public static void main(String[] args)
 94:     {
 95:         // Create an array of available items
 96:         Item[] availableItems =
 97:         {
 98:             new Item(6.0, 25.0),
 99:             new Item(8.0, 42.0),
100:             new Item(12.0, 60.0),
101:             new Item(18.0, 95.0)
102:         };

104:         // Prompt for the knapsack's maximum weight
105:         Scanner scnr = new Scanner(System.in);
106:         System.out.print("Enter maximum weight the knapsack can hold: ");
107:         double maxWeight = scnr.nextDouble();

109:         Knapsack knapsack = Knapsack.knapsack01(availableItems, maxWeight);

111:         // Show the objects in the knapsack
112:         System.out.println();
113:         System.out.println("Objects in knapsack:");
114:         int i = 1;
115:         double sumWeight = 0.0;
116:         double sumValue = 0.0;
117:         for (Item item : knapsack.getItems())
118:         {
119:             sumWeight += item.weight;
120:             sumValue += item.value;
121:             System.out.printf
122:             (
123:                 "%d: weight %d, value %d%n",
124:                 i,
125:                 (int)item.weight,
126:                 (int)item.value
127:             );
128:             i++;
129:         }
130:         System.out.println();

132:         System.out.printf
133:         (
134:             "Total weight of items in knapsack: %d%n",
135:             (int) sumWeight
136:         );
137:         System.out.printf
138:         (
139:             "Total value of items in knapsack: %d%n",
140:             (int) sumValue
141:         );
142:     }
143: }