Programming Language: Java

Programming Environment: Eclipse

Refer to the knapsack problem. You can also refer to CLRS for more info on the problem definition. In addition to returning an array with the included items, you should also update the class variable best_value with the optimal value in a solution.

The program expects three inputs: Name of the text file which lists the values and weights of the items Weight of the knapsack, W A character input for the algorithm by a list of integers to sort: [d] for dynamic, [g] for greedy and [e] for enumeration.

Instruction: edit the TODO part of the code only, every after the "do not edit" comment, don't edit. Make sure the code runs.

import java.io.File; import java.io.IOException; import java.util.ArrayList; import java.util.Arrays; import java.util.Scanner;

import edu.wit.cs.comp3370.LAB4.Item;

/* Provides a solution to the 0-1 knapsack problem * Dynamic programming and 0-1 Knapsack Problem */

public class LAB4 {

// TODO: document this method public static Item[] FindDynamic(Item[] table, int weight) { // TODO: implement this method // Return an instance of Item and update best_value

return null; }

/******************************************** * * You shouldn't modify anything past here * ********************************************/

public static class Item { public int weight; public int value; public int index;

public Item(int w, int v, int i) { weight = w; value = v; index = i; }

public String toString() { return "(" + weight + "#, $" + value + ")"; } }

// set by calls to Find* methods private static int best_value = 0;

// enumerates all subsets of items to find maximum value that fits in // knapsack public static Item[] FindEnumerate(Item[] table, int weight) {

if (table.length > 63) { // bitshift fails for larger sizes System.err.println("Problem size too large. Exiting"); System.exit(0); }

int nCr = 1 << table.length; // bitmask for included items int bestSum = -1; boolean[] bestUsed = {}; boolean[] used = new boolean[table.length];

for (int i = 0; i < nCr; i++) { // test all combinations int temp = i;

for (int j = 0; j < table.length; j++) { used[j] = (temp % 2 == 1); temp = temp >> 1; }

if (TotalWeight(table, used) <= weight) { if (TotalValue(table, used) > bestSum) { bestUsed = Arrays.copyOf(used, used.length); bestSum = TotalValue(table, used); } } }

int itemCount = 0; // count number of items in best result for (int i = 0; i < bestUsed.length; i++) if (bestUsed[i]) itemCount++;

Item[] ret = new Item[itemCount]; int retIndex = 0;

for (int i = 0; i < bestUsed.length; i++) { // construct item list if (bestUsed[i]) { ret[retIndex] = table[i]; retIndex++; } } best_value = bestSum; return ret;

}

// returns total value of all items that are marked true in used array private static int TotalValue(Item[] table, boolean[] used) { int ret = 0; for (int i = 0; i < table.length; i++) if (used[i]) ret += table[i].value;

return ret; }

// returns total weight of all items that are marked true in used array private static int TotalWeight(Item[] table, boolean[] used) { int ret = 0; for (int i = 0; i < table.length; i++) { if (used[i]) ret += table[i].weight; }

return ret; }

// adds items to the knapsack by picking the next item with the highest // value:weight ratio. This could use a max-heap of ratios to run faster, // but // it runs in n^2 time wrt items because it has to scan every item each time // an item is added public static Item[] FindGreedy(Item[] table, int weight) { boolean[] used = new boolean[table.length]; int itemCount = 0;

while (weight > 0) { // while the knapsack has space int bestIndex = GetGreedyBest(table, used, weight); if (bestIndex < 0) break; weight -= table[bestIndex].weight; best_value += table[bestIndex].value; used[bestIndex] = true; itemCount++; }

Item[] ret = new Item[itemCount]; int retIndex = 0;

for (int i = 0; i < used.length; i++) { // construct item list if (used[i]) { ret[retIndex] = table[i]; retIndex++; } }

return ret; }

// finds the available item with the best value:weight ratio that fits in // the knapsack private static int GetGreedyBest(Item[] table, boolean[] used, int weight) {

double bestVal = -1; int bestIndex = -1; for (int i = 0; i < table.length; i++) { double ratio = (table[i].value * 1.0) / table[i].weight; if (!used[i] && (ratio > bestVal) && (weight >= table[i].weight)) { bestVal = ratio; bestIndex = i; } }

return bestIndex; }

public static int getBest() { return best_value; }

public static void main(String[] args) { Scanner s = new Scanner(System.in); String file1; int weight = 0; System.out.printf( "Enter , ([d]ynamic programming, [e]numerate, [g]reedy). "); System.out.printf("The class example is provided as: objects/small0 5 d "); // System.out.printf("objects/small0 5 d "); file1 = s.next(); weight = s.nextInt();

ArrayList tableList = new ArrayList();

try (Scanner f = new Scanner(new File(file1))) { int i = 0; while (f.hasNextInt()) tableList.add(new Item(f.nextInt(), f.nextInt(), i++)); } catch (IOException e) { System.err.println("Cannot open file " + file1 + ". Exiting."); System.exit(0); }

Item[] table = new Item[tableList.size()]; for (int i = 0; i < tableList.size(); i++) table[i] = tableList.get(i);

String algo = s.next(); Item[] result = {};

switch (algo.charAt(0)) { case 'd': result = FindDynamic(table, weight); break; case 'e': result = FindEnumerate(table, weight); break; case 'g': result = FindGreedy(table, weight); break; default: System.out.println("Invalid algorithm"); System.exit(0); break; }

s.close();

System.out.printf("Index of included items: "); for (int i = 0; i < result.length; i++) System.out.printf("%d ", result[i].index); System.out.printf(" Best value: %d ", best_value); }

}