Suppose you are given a set S of tuples = {(v_1, p_1), (v_2, p_2), ..., (v_n, p_

Question

Suppose you are given a set S of tuples = {(v_1, p_1), (v_2, p_2), ..., (v_n, p_n)} and an integer X. Your goal is to a find a set T {1, 2, ..., n} such that sigma_i elementof T p_i is maximized (over all possible choices of T) subject to the constraints sigma_i T v_i lessthanorequalto X. Your goal is to design an algorithm, using Dynamic Programming, that gets S and X as input, and outputs such T. Write the recurrence relation for this problem. Design an iterative algorithm (based on the recurrence relation) to solve the problem. Analyze the run-time of your algorithm.

Explanation / Answer

(i)

We wanted to find a subset of S having maximum to weight. So always calculating maximum
weight-value pairs.
Recurrence relation will be..

cost[ i, w ] = cost[ i – 1, w ] if, Wi > w
cost[ i, w ] = max( cost[ i – 1, w ], cost[ i – 1, w – Wi ] ) if, Wi <= w

(ii)

MaximizeTupleDP(v,w,n,X)
{
   for(w=0 to X)DP[0,w] = 0;
       for(j=1 to n)
           for(w=0 to X)
               if(w[j] <= w)
DP[j,w] = max{DP[j-1,w],v[j]+DP[j-1,w-w[j]]};
               else
DP[j,w] = DP[j-1,w];
   return DP[n,X];          
}

(iii)

Complexity O(n*X)

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

---

---

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