Java: Documenting this method Please help me explain this code line by line by h
ID: 3858449 • Letter: J
Question
Java: Documenting this method
Please help me explain this code line by line by helping me document this method above the "// TODO: document this method" in the code below for knapsack. Do not comment on the code where it says "You shouldn't modify anything past here" and anything below it, just the codes that are bolded. I already implemented the method, but just need help documenting the method for knapsack line by line.
The code works, but I need help understanding what this program does. It is bolded in the code below. Document this method.
----------------------------------------------------------------------------------------------------------
Source Code:
public class LAB4 {
// TODO: document this method
public static Item[] FindDynamic(Item[] table, int weight) {
// Return an instance of Item and update best_value
int[][] values = new int[table.length + 1][weight + 1];
int[][] keeps = new int[table.length + 1][weight + 1];
best_value = 0; // best value is initialized to zero every time this
// method is run in order to make sure the global best
// value starts from 0 every time this method is run.
for (int i = 0; i < values[0].length; i++) {
values[0][i] = 0;
}
for (int i = 1; i <= table.length; i++) {
for (int j = 1; j <= weight; j++) {
if (table[i - 1].weight <= j) {
if (table[i - 1].value + values[i - 1][j - table[i - 1].weight] > values[i - 1][j]) {
values[i][j] = table[i - 1].value + values[i - 1][j - table[i - 1].weight];
keeps[i - 1][j] = 1;
} else {
values[i][j] = values[i - 1][j];
}
} else {
values[i][j] = values[i - 1][j];
}
}
}
Item[] newkeep = new Item[table.length]; // adds all keep values with 1
// to the newkeep knapsack
// of type item.
int num = 0;
for (int i = table.length - 1; i >= 0; i--) {
if (keeps[i][weight] == 1) {
newkeep[num] = table[i];
num++;
best_value += table[i].value;
weight -= table[i].weight;
}
}
Item[] finalsack = new Item[num]; // adding values to this knapsack
// because the newkeep sack has
// extra empty spaces. also why num
// counter is needed.
for (int i = 0; i < num; i++) {
finalsack[i] = newkeep[i];
}
return finalsack;
}
/********************************************
*
* 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 <objects file> <knapsack weight> <algorithm>, ([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<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 value: %d ", best_value);
}
}
Explanation / Answer
public class LAB4 {
// TODO: document this method
public static Item[] FindDynamic(Item[] table, int weight) {
// Return an instance of Item and update best_value
// declare values matrix. values[m][n] represent the best value for the knapsack with weigth- n and there are first m items from the table
int[][] values = new int[table.length + 1][weight + 1];
// declare keeps matrix. keeps[m][n] represent whether for the best value for the knapsack with weigth- n, item m-1 is kept in the knapsack or not. It will be set to 1 if it is kept.
int[][] keeps = new int[table.length + 1][weight + 1];
best_value = 0; // best value is initialized to zero every time this
// method is run in order to make sure the global best
// value starts from 0 every time this method is run.
// initiate all values of the form values[0][i]. Because values[0][i] for i = 0 to weight indicates best value for knapsack when no items are available to pick-up from (as described above), hence values[0][i] for all i is 0.
for (int i = 0; i < values[0].length; i++) {
values[0][i] = 0;
}
for (int i = 1; i <= table.length; i++) { // look at all items one by one, i represents the item number being looked at
for (int j = 1; j <= weight; j++) { // assume weight of knapsack from 1 to the given 'weight', j represents the assumed weight
if (table[i - 1].weight <= j) { // if weight of the current item is less than the assumed weight, consider adding it to the knapsack
// if the item is ignored, that is not added to the knapsack, the best value for knapsack with weight j is values[i - 1][j]
// to accomodate the current item look at the knapsack with weight assumed weight minus the weight of current item, that is, j - table[i - 1].weight. The best value for this knapsack without the current item is values[i - 1][j - table[i - 1].weight]. Then if we increase the weight to j and add the current item to this knapsack, the value will be table[i - 1].value + values[i - 1][j - table[i - 1].weight]
if (table[i - 1].value + values[i - 1][j - table[i - 1].weight] > values[i - 1][j]) { // if the current item is accomodated into the knapsack and the value table[i - 1].value + values[i - 1][j - table[i - 1].weight] is better than not adding the current item
// update values[i][j] by considering adding the current item
values[i][j] = table[i - 1].value + values[i - 1][j - table[i - 1].weight];
// since we have kept this item for assumed weight j, update keeps[i-1][j]
keeps[i - 1][j] = 1;
} else { // if the current item is accomodated into the knapsack and the value table[i - 1].value + values[i - 1][j - table[i - 1].weight] is not any better than not adding the current item
// don't add item to the knapsack, the best value is equivalent to values[i - 1][j]
values[i][j] = values[i - 1][j];
}
} else { // if weight of the current item is more than the assumed weight, it cannot be added to the knapsack, there is no point considering adding this item
// the best value is as good as not considering this item exists and hence the best value for knapsack with items from 0 to i-1 and the assumes weight j
values[i][j] = values[i - 1][j];
}
}
}
// newkeep will store all items that are in the knapsack with the weight 'weight' and all items in the table
Item[] newkeep = new Item[table.length]; // adds all keep values with 1
// to the newkeep knapsack
// of type item.
// num keeps track of the number of items in the knapsack
int num = 0;
// we look at each item starting from last item to first
for (int i = table.length - 1; i >= 0; i--) {
if (keeps[i][weight] == 1) { // if current item is in the knapsack
// add the current item to the the newkeep array
newkeep[num] = table[i];
// update the number of elements in knapsack, increment it by 1
num++;
// update best value, increment it by item value, since this item is in the knapsack
best_value += table[i].value;
// update the remaining weight capacity, decrement it by item weight, since now the knapsack capacity is reduced becase we kept the current item
weight -= table[i].weight;
}
}
// we want a amaller array finalstack with the required length as all array values beyond num are empty
Item[] finalsack = new Item[num]; // adding values to this knapsack
// because the newkeep sack has
// extra empty spaces. also why num
// counter is needed.
// look at the first num items from newkeep and copy them into finalsack
for (int i = 0; i < num; i++) {
finalsack[i] = newkeep[i];
}
// finally return the final sack
return finalsack;
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.