class Item
class ItemRatioComparator implements Comparator
class Knapsack
public class FractionalKnapsackDemo
1: //FractionalKnapsackDemo.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;
12: public double fraction;
14: Item
15: (
16: double itemWeight,
17: double itemValue
18: )
19: {
20: weight = itemWeight;
21: value = itemValue;
22: fraction = 1.0;
23: }
24: }
26: class ItemRatioComparator implements Comparator<Item>
27: {
28: public int compare
29: (
30: Item item1,
31: Item item2
32: )
33: {
34: double item1Ratio = item1.value / item1.weight;
35: double item2Ratio = item2.value / item2.weight;
36: if (item1Ratio < item2Ratio)
37: {
38: return 1;
39: }
40: else if (item1Ratio > item2Ratio)
41: {
42: return -1;
43: }
44: return 0;
45: }
46: }
48: class Knapsack
49: {
50: private double maxWeight;
51: private ArrayList<Item> items;
53: Knapsack(double maximumWeight)
54: {
55: maxWeight = maximumWeight;
56: items = new ArrayList<Item>();
57: }
59: public ArrayList<Item> getItems()
60: {
61: return this.items;
62: }
64: public double getMaxWeight()
65: {
66: return maxWeight;
67: }
69: public static Knapsack fractionalKnapsack
70: (
71: Item[] availableItems,
72: double maxWeight
73: )
74: {
75: // Sort the items in descending order based on value/weight
76: Arrays.sort(availableItems, new ItemRatioComparator());
78: // Initialize a new knapsack to hold items
79: Knapsack knapsack = new Knapsack(maxWeight);
81: double remaining = maxWeight;
82: for (Item item : availableItems)
83: {
84: // Check if the full item can fit into the knapsack or
85: // only a fraction
86: if (item.weight <= remaining)
87: {
88: // The full item will fit
89: knapsack.getItems().add(item);
90: remaining -= item.weight;
91: }
92: else if (remaining > 0)
93: {
94: // Only a fractional part of the item will fit. Add that
95: // fraction of the item, and then exit.
96: item.fraction = remaining / item.weight;
97: knapsack.getItems().add(item);
98: break;
99: }
100: }
102: return knapsack;
103: }
104: }
106: public class FractionalKnapsackDemo
107: {
108: public static void main(String[] args)
109: {
110: // Create an ArrayList of available items
111: Item[] availableItems =
112: {
113: new Item(6.0, 25.0),
114: new Item(8.0, 42.0),
115: new Item(12.0, 60.0),
116: new Item(18.0, 95.0)
117: };
119: // Prompt for the knapsack's maximum weight
120: Scanner scnr = new Scanner(System.in);
121: System.out.print("Enter maximum weight the knapsack can hold: ");
122: double maxWeight = scnr.nextDouble();
124: Knapsack knapsack = Knapsack.fractionalKnapsack
125: (
126: availableItems,
127: maxWeight
128: );
130: // Show the objects in the knapsack
131: System.out.println("Objects in knapsack");
132: int i = 1;
133: double sumWeight = 0.0;
134: double sumValue = 0.0;
135: for (Item item : knapsack.getItems())
136: {
137: sumWeight += item.weight * item.fraction;
138: sumValue += item.value * item.fraction;
139: System.out.printf
140: (
141: "%d: %.1f of weight %.1f, value %.1f%n",
142: i,
143: item.fraction,
144: item.weight,
145: item.value * item.fraction
146: );
147: i++;
148: }
149: System.out.println();
151: System.out.printf
152: (
153: "Total weight of items in knapsack: %d%n",
154: (int) sumWeight
155: );
156: System.out.printf
157: (
158: "Total value of items in knapsack: %d%n",
159: (int) sumValue
160: );
161: }
162: }