Problem 2 [50 points] Consider the following more general version of the Knapsac

Question

Problem 2 [50 points] Consider the following more general version of the Knapsack problem. There are p groups of objects O1, O2,.. ., Op and a knapsack capacity W. Each object x has a weight wz and a value vx. Our goal is to select a subset of objects such that: .the total weights of selected objects is at most W, at most one object is selected from any group, and the total value of the selected objects is maximized Suppose that n is the total number of objects in all the groups and V is the maximum value of any object, i.e., V- . max . ar. Give an O(nW) time algorithm for this general Knapsack problem. Explain why your algorithm is correct and analyze the running time of your algorithm. Hint: Do a dynamic programming with increasing Knapsack capacity. z is an object "

Explanation / Answer

Let's learn about dynamic programming first.
Dynamic programming is a method for solving
optimization problems.
The idea: Compute the solutions to the subsub-problems
once and store the solutions in a table, so that they
can be reused (repeatedly) later.
Remark: We trade space for time.
STEPS TO USE DYNAMIC PROGRAMMING:

Step1: Structure: Characterize the structure of an
optimal solution.
– Decompose the problem into smaller problems,
and find a relation between the structure of the
optimal solution of the original problem and the
solutions of the smaller problems.
Step2: Principle of Optimality: Recursively define the
value of an optimal solution.
– Express the solution of the original problem in
terms of optimal solutions for smaller problems.
Step 3: Bottom-up computation: Compute the value
of an optimal solution in a bottom-up fashion by
using a table structure.
Step 4: Construction of optimal solution: Construct
an optimal solution from computed information.
SUPPOSE TAKE AN EXAMPLE:
Let W=10
and
i 1 2 3 4
v(i) 10 40 30 50
w(i) 5 4 6 3

V[i,w] 0 1 2 3 4 5 6 7 8 9 10
i =0 0 0 0 0 0 0 0 0 0 0 0
i =1 1 0 0 0 0 0 10 10 10 10 10 10
i= 2 2 0 0 0 0 40 40 40 40 40 50 50
i=3 3 0 0 0 0 40 40 40 40 40 50 70
i=4 4 0 0 0 50 50 50 50 90 90 90 90

Remarks:
1. The final output is V[4,10]=90//RESULT IS CALCULATED THROUGH BELOW IMPLEMENTATION
2.The method described does not tell which subset gives the
optimal solution. (It is {2,4} in this example).
ALGORITHIMIC IMPLEMENTATION OF KNAPSACK WITH EXANMPLE IN JAVA::::

// A Dynamic Programming based solution for Knapsack problem
class KnapsackpROBLEM
{
// 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 knapSackcALCULATE(int W, int wt[], int val[], int n)
{
int i, w;
int K[][] = new int[n+1][W+1];// CREATE A TABLE TO STORE INTERMEDIATE VALUES
// Build table K[][] in bottom up manner
//recomputations of same subproblems can be avoided by constructing a temporary array K[][].
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];
}

// Driver program to test above function
public static void main(String args[])
{
int val[] = new int[]{10,40,30,50};
int wt[] = new int[]{5,4,6,3};
int W = 10;
int n = val.length;
System.out.println(knapSackcALCULATE(W, wt, val, n));
}
}
TIME COMPLEXITY:::
Run time = (time to solve each subproblem)*(number of unique subproblems)
For knapsack,
Outdegree of each vertex is at most 2 i.e O(1).
Now if we check the subproblems, we can find some pattern,
The subproblem `(n,W)` depends on `(n-1,W)` and `(n-1,W-w(n))`.
`(n-1,W)` depends on `(n-2,W)` and `(n-2,W-w(n-1))`
`(n-1,W-w(n))` depends on `(n-2,W-w(n))` and `(n-2,W-w(n)-w(n-1))`
Note that for each of the n items, the weight can vary at most 1 to W.
So there is at most n*W unique subproblems.
And as we solve each subproblem only once,
The running time = O(1)O(nW) = O(n*W).

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---

---

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