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 subsetorequalto {1, 2, ..., n} such that sigma _ I elementof T P_i is maximized (over all possible choices of T) subject to the constraint sigma_i Elementof 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) Here we are selecting maximum pair according 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)

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

(iii)

Complexity

Assume _WT as P

Complexity is O(nP)

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

---

---

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