Suppose you are given a set S of tuples = {langle upsilon_1, p_1 rangle, langle
ID: 3817312 • Letter: S
Question
Suppose you are given a set S of tuples = {langle upsilon_1, p_1 rangle, langle upsilon_2, p_2 rangle, ..., langle upsilon_n, p_n rangle} and an integer X. Your goal is to a find a set T SubsetEqual {1, 2, ..., n such that Sum_i elementof T p_i is maximized (over all possible choices of T) Subject to the constraint Sum_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. Your grade depends on the correctness and efficiency.Explanation / Answer
We are given X and tuples of the form < vi, pi >, problem is to find a subset such that the sum of all pi is maximum subject to the constraint that sum of all vi is less than or equal to X.
Recurrence relation
T(i,j) = Maximum sum using the first i items such that the sum of all vi is less than j
T(i,j) = max( T(i - 1, j) , T(i - 1, j - vi) + pi )
The above recurrence says for every item we have two option
Iterative algorithm
n -> number of tuples
for i from 1 to n
for j in range 1 to X
if i >= 1
T[i][j] = T[i-1][j]
if j - vi >= 0
T[i][j] = max( T[i][j] , T[i-1][j - vi] + pi )
Time complexity
since we have two nested for the time complexity is multiple of two loops
O(n * X)
where n is the number of tuples
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.