Knapsack problem
Implementation
The skeleton code on gitlab is the start of a program to solve the 0-1 knapsack problem. Givennobjects, each with integer weightwiand pricepi, and a knapsack that can holdup to weightW, select the most valuable subset of objects that don’t exceed the knapsack’s capacity. Allweights and prices will be positive integers. Implement a dynamic programming solution to the problem.
For this assignment, you will implement theFindDynamicmethod.
In addition to returning an array with the included items, you should also update the classvariablebestpricewith the optimal price in a solution.
There are two algorithms already implemented:
findEnumerate
Tests every possible subset for the weight limit and price of the knapsack.
findGreedy
Greedily picks the best remaining item based on its price:weight ratio, which is sometimessuboptimal.
The item files are supplied in theobjectsdirectory. They are text files with a〈
weight price〉pair to describean item on each line.
Testing
The tests checkif the knapsack has the optimal price and satisfies the weight limit.
AChartMakerclass is included, which will create a chart of runtimes comparing dynamic, enumerative,and greedy algorithms. You can use this chart to verify that your dynamic programming solution runtimeis what you expect.
packageedu.wit.cs.comp2350;
importjava.io.File;
importjava.io.IOException;
importjava.util.ArrayList;
importjava.util.Arrays;
importjava.util.Scanner;
/* Provides a solution to the 0-1 knapsack problem
*
*/
publicclassLAB8 {
// TODO: document this method
publicstaticItem[] FindDynamic(Item[] table, intweight) {
// TODO: implement this method
returnnull;
// TODO: set best_price to the sum of the optimal items’ prices
}
/********************************************
*
* You shouldn’t modify anything past here
*
********************************************/
// set by calls to Find* methods
privatestaticintbest_price = 0;
publicstaticclassItem {
publicintweight;
publicintprice;
publicintindex;
publicItem(intw, intp, inti) {
weight = w;
price = p;
index = i;
}
publicString toString() {
return”(“+ weight + “#, $”+ price + “)”;
}
}
// enumerates all subsets of items to find maximum price that fits in knapsack
publicstaticItem[] FindEnumerate(Item[] table, intweight) {
if(table.length> 31) { // bitshift fails for larger sizes
System.err.println(“Problem size too large. Exiting”);
System.exit(0);
}
intnCr = 1<<table.length; // bitmask for included items
intbestSum = -1;
boolean[] bestUsed = {};
boolean[] used = newboolean[table.length];
for(inti = 0; i <nCr; i++) { // test all combinations
inttemp = i;
for(intj = 0; j <table.length; j++) {
used[j] = (temp % 2== 1);
temp = temp >> 1;
}
if(TotalWeight(table, used) <= weight) {
if(TotalPrice(table, used) >bestSum) {
bestUsed = Arrays.copyOf(used, used.length);
bestSum = TotalPrice(table, used);
}
}
}
intitemCount = 0; // count number of items in best result
for(inti = 0; i <bestUsed.length; i++)
if(bestUsed[i])
itemCount++;
Item[] ret = newItem[itemCount];
intretIndex = 0;
for(inti = 0; i <bestUsed.length; i++) { // construct item list
if(bestUsed[i]) {
ret[retIndex] = table[i];
retIndex++;
}
}
best_price = bestSum;
returnret;
}
// returns total price of all items that are marked true in used array
privatestaticintTotalPrice(Item[] table, boolean[] used) {
intret = 0;
for(inti = 0; i <table.length; i++)
if(used[i])
ret += table[i].price;
returnret;
}
// returns total weight of all items that are marked true in used array
privatestaticintTotalWeight(Item[] table, boolean[] used) {
intret = 0;
for(inti = 0; i <table.length; i++) {
if(used[i])
ret += table[i].weight;
}
returnret;
}
// adds items to the knapsack by picking the next item with the highest
// price: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
publicstaticItem[] FindGreedy(Item[] table, intweight) {
boolean[] used = newboolean[table.length];
intitemCount = 0;
while(weight > 0) { // while the knapsack has space
intbestIndex = GetGreedyBest(table, used, weight);
if(bestIndex< 0)
break;
weight -= table[bestIndex].weight;
best_price += table[bestIndex].price;
used[bestIndex] = true;
itemCount++;
}
Item[] ret = newItem[itemCount];
intretIndex = 0;
for(inti = 0; i <used.length; i++) { // construct item list
if(used[i]) {
ret[retIndex] = table[i];
retIndex++;
}
}
returnret;
}
// finds the available item with the best price:weight ratio that fits in
// the knapsack
privatestaticintGetGreedyBest(Item[] table, boolean[] used, intweight) {
doublebestVal = -1;
intbestIndex = -1;
for(inti = 0; i <table.length; i++) {
doubleratio = (table[i].price*1.0)/table[i].weight;
if(!used[i] && (ratio >bestVal) && (weight >= table[i].weight)) {
bestVal = ratio;
bestIndex = i;
}
}
returnbestIndex;
}
publicstaticintgetBest() {
returnbest_price;
}
publicstaticvoidmain(String[] args) {
Scanner s = newScanner(System.in);
String file1;
intweight = 0;
System.out.printf(“Enter <objects file><knapsack weight><algorithm>, ([d]ynamic programming, [e]numerate, [g]reedy).\n”);
System.out.printf(“(e.g: objects/small 10 g)\n”);
file1 = s.next();
weight = s.nextInt();
ArrayList<Item>tableList = newArrayList<Item>();
try(Scanner f = newScanner(newFile(file1))) {
inti = 0;
while(f.hasNextInt())
tableList.add(newItem(f.nextInt(), f.nextInt(), i++));
} catch(IOException e) {
System.err.println(“Cannot open file “+ file1 + “. Exiting.”);
System.exit(0);
}
Item[] table = newItem[tableList.size()];
for(inti = 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(inti = 0; i <result.length; i++)
System.out.printf(“%d “, result[i].index);
System.out.printf(“\nBest total price: %d\n”, best_price);
}
}
Solution
//package edu.wit.cs.comp2350; import java.io.File; import java.io.IOException; import java.util.ArrayList; import java.util.Arrays; import java.util.Scanner; import java.util.List; /* Provides a solution to the 0-1 knapsack problem * * Wentworth Institute of Technology * COMP 2350 * Lab Assignment 8 * */ public class LAB8 { // TODO: document this method public static ArrayList FindDynamic1(intW,int[] val,int[] wt,int n){ // to solve sub-problem using dynamic programming used two-Dimension array K[][] // which will store the index of the and price values in the arraylist // to find the index of the weight or prices ued backtracking int i, w; int K[][] = new int[n+1][W+1]; int[] selected = new int[n+1]; ArrayList al = new ArrayList(); for (i = 0; i <= n; i++){ for (w = 0; w <= W; w++){ if (i==0 || w==0) K[i]
[w]
= 0; else if (wt[i-1] <= w) K[i]
[w]
= Math.max(val[i-1] + K[i-1][w-wt[i-1]], K[i-1]
[w]
); else K[i]
[w]
= K[i-1]
[w]
; } } inttempW = W; int y = 0; //to index in selected for (int x = n; x > 0; x–){ if ((tempW-wt[x-1] >= 0) && (K[x][tempW] – K[x-1][tempW-wt[x-1]] == val[x-1]) ){ selected[y++] = x-1; //store current index and increment y tempW-=wt[x-1]; } } for(int j = y-1; j >= 0; j–){ al.add(selected[j]); /*System.out.print(“#” + (selected[j]+1) + ” “); //System.out.println(val[selected[j]]); */ } best_price = K[n][W]; return al; } public static Item[] FindDynamic(Item[] table, int weight) { int n = table.length; int[] weight_array = new int[table.length]; // done in using two arrays 1 for weight and another for price int[] price_array = new int[table.length]; for(int i=0;i list = FindDynamic1(weight,price_array,weight_array,n); Item[] ret = new Item[list.size()]; for(Integer i1:list){ Item a = new Item(0,0,0); a.index = i1; ret[list.indexOf(i1)] = a; } return ret; } // TODO: implement this method // TODO: set best_price to the sum of the optimal items’ prices // TODO: set best_price to the sum of the optimal items’ prices /******************************************** * * You shouldn’t modify anything past here * ********************************************/ // set by calls to Find* methods private static intbest_price = 0; public static class Item { public int weight; public int price; public int index; public Item(int w, int p, int i) { weight = w; price = p; index = i; } public String toString() { return “(” + weight + “#, $” + price + “)”; } } // enumerates all subsets of items to find maximum price that fits in knapsack public static Item[] FindEnumerate(Item[] table, int weight) { if (table.length> 31) { // bitshift fails for larger sizes System.err.println(“Problem size too large. Exiting”); System.exit(0); } intnCr = 1 <<table.length; // bitmask for included items intbestSum = -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 (TotalPrice(table, used) >bestSum) { bestUsed = Arrays.copyOf(used, used.length); bestSum= TotalPrice(table, used); } } } intitemCount = 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]; intretIndex = 0; for (int i = 0; i <bestUsed.length; i++) { // construct item list if (bestUsed[i]) { ret[retIndex] = table[i]; retIndex++; } } best_price = bestSum; return ret; } // returns total price of all items that are marked true in used array private static intTotalPrice(Item[] table, boolean[] used) { int ret = 0; for (int i = 0; i <table.length; i++) if (used[i]) ret += table[i].price; return ret; } // returns total weight of all items that are marked true in used array private static intTotalWeight(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 // price: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]; intitemCount = 0; while (weight > 0) { // while the knapsack has space intbestIndex = GetGreedyBest(table, used, weight); if (bestIndex< 0) break; weight -= table[bestIndex].weight; best_price += table[bestIndex].price; used[bestIndex] = true; itemCount++; } Item[] ret = new Item[itemCount]; intretIndex = 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 price:weight ratio that fits in // the knapsack private static intGetGreedyBest(Item[] table, boolean[] used, int weight) { double bestVal = -1; intbestIndex = -1; for (int i = 0; i <table.length; i++) { double ratio = (table[i].price*1.0)/table[i].weight; if (!used[i] && (ratio >bestVal) && (weight >= table[i].weight)) { bestVal = ratio; bestIndex = i; } } return bestIndex; } public static intgetBest() { return best_price; } 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).\n”); System.out.printf(“(e.g: objects/small 10 g)\n”); file1 = s.next(); weight = s.nextInt(); ArrayListtableList = new ArrayList(); File file = new File(file1); try { Scanner f = new Scanner(file); 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(“\nBest total price: %d\n”, best_price); } }