**Has to use this method found in the code below.** public static Item[] FindDyn
ID: 3739224 • Letter: #
Question
**Has to use this method found in the code below.**
public static Item[] FindDynamic(Item[] table, int weight) {
// TODO: implement this method
// TODO: set best_price to the sum of the optimal items' prices
return new Item[]{};
*************************************************************************
The skeleton code on gitlab is the start of a program to solve the 0-1 knapsack problem (p425 in CLRS, and lecture notes): Given n objects, each with integer weight wi and price pi , and a knapsack that can hold up to weight W, select the most valuable subset of objects that don’t exceed the knapsack’s capacity. All weights and prices will be positive integers. Implement a dynamic programming solution to the problem. For this assignment, you will implement the FindDynamic method (and any helper methods you want) in LAB8.java. In addition to returning an array with the included items, you should also update the class variable best price with 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 sometimes suboptimal. The item files are supplied in the objects directory. They are text files with a hweight pricei pair to describe an item on each line.
import java.io.File;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;
/*
* Provides a solution to the 0-1 knapsack problem
*
*
*/
public class LAB8 {
// TODO: document this method
public static Item[] FindDynamic(Item[] table, int weight) {
// TODO: implement this method
// TODO: set best_price to the sum of the optimal items' prices
return new Item[]{};
}
/********************************************
*
* You shouldn't modify anything past here
*
********************************************/
// set by calls to Find* methods
private static int best_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);
}
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 (TotalPrice(table, used) > bestSum) {
bestUsed = Arrays.copyOf(used, used.length);
bestSum = TotalPrice(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_price = bestSum;
return ret;
}
// returns total price of all items that are marked true in used array
private static int TotalPrice(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 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
// 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];
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_price += table[bestIndex].price;
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 price: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].price*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_price;
}
public static void main(String[] args) {
Scanner s = new Scanner(System.in);
String file1;
int weight = 0;
System.out.printf("Enter <objects file> <knapsack weight> <algorithm>, ([d]ynamic programming, [e]numerate, [g]reedy). ");
System.out.printf("(e.g: objects/small 10 g) ");
file1 = s.next();
weight = s.nextInt();
ArrayList<Item> tableList = new ArrayList<Item>();
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 total price: %d ", best_price);
}
}
Explanation / Answer
The solution to the problem is
class knapsack
{
static int max(int a, int b) { return (a > b)? a : b; }
static int knapSack(int w, int wt[], int item[], int n)
{
if (n == 0 || w == 0)
return 0;
if (wt[n-1] > w)
return knapSack(w, wt, item, n-1);
else return max( val[n-1] + knapSack(w-wt[n-1], wt, item, n-1),
knapSack(w, wt, item, n-1)
);
}
public static void main(String args[])
{
int item[] = new int[]{60, 100, 120};
int wt[] = new int[]{10, 20, 30};
int w = 50;
int n = item.length;
System.out.println(knapSack(w, wt, val, n));
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.