We studied the knapsack problem and solved it using recursion. Let us say the va

Question

We studied the knapsack problem and solved it using recursion. Let us say the values are arranged in two dimensional array instead. The thief wants to start anywhere, pick up a series of items (by going up, down, left or right after picking up each item) and hopes for the total to match the target value. Here are a few examples using 4x4 array. Items in GREEN are selected & they total to specified target value in each case.

Develop your program to find whether a perfect match exists for a given target value. not necessary to output selected items or their position

22:11 nd it using mcc Let us say the valucs ar: arrange: in two dim:nso1al array c thic s to start anywhc Etc pick up a series of Items iby going up, down, left or right a ter p king up each item) a hopes for the tots to match the target value. llers are e few exemples uslng 4x4 arrey. Items In GR N are selected & they totelto is 20 4 9 57 32 7 24 ir:

Explanation / Answer

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)
{
// Base Case
if (n == 0 || W == 0)
return 0;
  
// If weight of the nth item is more than Knapsack capacity W, then
// this item cannot be included in the optimal solution
if (wt[n-1] > W)
return knapSack(W, wt, val, n-1);
  
// Return the maximum of two cases:
// (1) nth item included
// (2) not included
else return max( val[n-1] + knapSack(W-wt[n-1], wt, val, n-1),
knapSack(W, wt, val, n-1)
);
}


// Driver program to test above function
public static void main(String args[])
{
int val[] = new int[]{Val};
int wt[] = new int[]{Wt Val};
int W = 50;
int n = val.length;
System.out.println(knapSack(W, wt, val, n));
}
}

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[]{15,31,4,18,23,43,17,9};
int wt[] = new int[]{10, 20, 30};
int W = 50;
int n = val.length;
System.out.println(knapSack(W, wt, val, n));
}
}
public static void main(String args[])
{
int val[] = new int[]{7,4,18,20};
int wt[] = new int[]{10, 20, 30};
int W = 50;
int n = val.length;
System.out.println(knapSack(W, wt, val, n));
}
}
public static void main(String args[])
{
int val[] = new int[]{4,7,24,9,17,3};
int wt[] = new int[]{10, 20, 30};
int W = 50;
int n = val.length;
System.out.println(knapSack(W, wt, val, n));
}
}
public static void main(String args[])
{
int val[] = new int[]{24,1,2,45};
int wt[] = new int[]{10, 20, 30};
int W = 50;
int n = val.length;
System.out.println(knapSack(W, wt, val, n));
}
}

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.