Consider the 0-1 knapsack problem, in which we are given a set of n objects (w[i
ID: 3803026 • Letter: C
Question
Consider the 0-1 knapsack problem, in which we are given a set of n objects (w[i], b[i]), where w[i] and b[i] are the weight and profit of object i respectively, and knapsack limit W.
(a) Design a backtracking algorithm to output the total profits for all possible subsets, ignoring knapsack limit W. What is the time complexity of your algorithm? (b) Design a backtracking algorithm to output the total profit of the subset of objects with the maximum total profit and with the total weight not greater than W. What is the time complexity of your algorithm?
Explanation / Answer
A)* Recursive implementation of 0-1 Knapsack problem *
class Knapsack
{
//An utility capacity that profits greatest of two whole numbers
static int max(int a, int b) { return (a > b)? a : b; }
//Returns the greatest esteem that can be placed in a knapsack of limit 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 thing is more than Knapsack limit W, then
//this thing can't be incorporated into the ideal arrangement
if (wt[n-1] > W)
return knapSack(W, wt, val, n-1);
//Return the most extreme of two cases:
//(1) nth thing included
//(2) excluded
else return max( val[n-1] + knapSack(W-wt[n-1], wt, val, n-1),
knapSack(W, wt, val, n-1)
);
}
B) //Driver program to test above capacity
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));
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.