Given a set of n positive integers, C = {c1,c2, ..., cn} and a positive integer K, is there a subset of C whose elements sum to K? A dynamic program for solving this problem uses a 2-dimensional Boolean table T, with n rows and k + 1 columns. T[i,j] 1≤ i ≤ n, 0 ≤ j ≤ K, is TRUE if and only if there is a subset of C = {c1,c2, ..., ci} whose elements sum to j. Which of the following is valid for 2 ≤ i ≤ n, ci ≤ j ≤ K? a) ?[?, ?] = ( ?[? − 1, ?] ?? ?[?, ? − ?? ]) b) ?[?, ?] = ( ?[? − 1, ?] ??? ?[?, ? − ?? ]) c) ?[?, ?] = ( ?[? − 1, ?] ?? ?[? − 1, ? − ?? ]) d) ?[?, ?] = ( ?[? − 1, ?] ??? ?[? − 1, ? − ?? ])
Given a set of n positive integers, C = {c1,c2, ..., cn} and a positive integer K, is there a subset of C whose elements sum to K? A dynamic
a) ?[?, ?] = ( ?[? − 1, ?] ?? ?[?, ? − ?? ])
b) ?[?, ?] = ( ?[? − 1, ?] ??? ?[?, ? − ?? ])
c) ?[?, ?] = ( ?[? − 1, ?] ?? ?[? − 1, ? − ?? ])
d) ?[?, ?] = ( ?[? − 1, ?] ??? ?[? − 1, ? − ?? ])
In the above problem, which entry of the table T, if TRUE, implies that there is a subset whose elements sum to K?
a) ?[1, ? + 1]
b) ?[?, ?]
c) ?[?, 0]
d) ?[?, ? + 1]
Step by step
Solved in 2 steps