Design a dynamic programming algorithm to solve the sum of subsets problem: Problem statement: There are...

Transcribed Image Text:

Design a dynamic programming algorithm to solve the sum of subsets problem: Problem statement: There are n positive integers A = [a1, a2, ..., an] and a positive integer sum S. Is there a subset of A such that the sum of the integers in the subset is S. If there is such a subset, the output of the program is true, otherwise it is false. Example: • A = [3,5,11] and S = 16. In this case the output is true since 5 + 11 = 16 " A = [3,5,11] and S = 18. In this case the output is false since there is no solution. A = [3,5,11,15,22,] and S = 30. In this case the output is true since 3 +5 +22 = 30 This problem can be solved with dynamic programming. 1) Define the optimal substructure, and write the recurrence for the solution. [5%] 2) Write pseudo code, and apply dynamic programming to the following problem: A = [1,2,4] and S = 6. Show your dynamic programming table. [5%] Design a dynamic programming algorithm to solve the sum of subsets problem: Problem statement: There are n positive integers A = [a1, a2, ..., an] and a positive integer sum S. Is there a subset of A such that the sum of the integers in the subset is S. If there is such a subset, the output of the program is true, otherwise it is false. Example: • A = [3,5,11] and S = 16. In this case the output is true since 5 + 11 = 16 " A = [3,5,11] and S = 18. In this case the output is false since there is no solution. A = [3,5,11,15,22,] and S = 30. In this case the output is true since 3 +5 +22 = 30 This problem can be solved with dynamic programming. 1) Define the optimal substructure, and write the recurrence for the solution. [5%] 2) Write pseudo code, and apply dynamic programming to the following problem: A = [1,2,4] and S = 6. Show your dynamic programming table. [5%]

Answer rating: 100% (QA)

Here are the key points for implementing the Subset Sum Problem using recurrence relation Recurrence Relation Define the recurrence relation as follows isSubsetSumset n sum isSubsetSumset n1 sum or is... View the full answer