180k views
2 votes
Given a set S = {a1, a2, ..., an} of positive integers (denoting asset values), Set partitioning requires to partition S into two subsets S1 and S2 that minimizes the difference in the total (asset) values of S1 and S2. Identify a dynamic programming (DP) algorithm for the Set partition problem. Clarify all relevant details, justifying the DP formulation, and analyze your time-complexity. Illustrate the working of your DP algorithm, partitioning this example set S = {10, 6, 4, 4, 4, 3}

1 Answer

3 votes

Answer:

See the pictures attached

Step-by-step explanation:

Given a set S = {a1, a2, ..., an} of positive integers (denoting asset values), Set-example-1
Given a set S = {a1, a2, ..., an} of positive integers (denoting asset values), Set-example-2
User Mohas
by
3.9k points