Java: Documenting this method Please help me explain this code line by line by h
ID: 3858218 • 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. 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;
}
Explanation / Answer
//NOTE: Your code does NOTcompile, hard to explain the flow. Insted consider the following program which is well documented.
//START>>
// A Dynamic Programming based solution for 0-1 Knapsack problem
class Knapsack {
// A utility function that returns maximum of two integers
static int max(int a, int b) {
return (a > b) ? a : b;
}
// Returns the maximum value that can be put in a knapsack of capacity W
static int knapSack(int W, int wt[], int val[], int n) {
int i, w;
int K[][] = new int[n + 1][W + 1];
// Build table K[][] in bottom up manner
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] = max(val[i - 1] + K[i - 1][w - wt[i - 1]],
K[i - 1][w]);
else
K[i][w] = K[i - 1][w];
}
}
return K[n][W];
}
public static void main(String args[]) {
int val[] = new int[] { 60, 100, 120 };
int wt[] = new int[] { 10, 20, 30 };
int W = 50;
int n = val.length;
System.out.println(knapSack(W, wt, val, n));
}
}
// END>>
In case you have not understood how overlapping subproblems propery is take care by above algorithm, see the illustration below.
Cheers!
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.