minimum partition Algorithm

The minimum partition algorithm is a computational technique used to solve the partition problem, which is a classical problem in computer science and mathematics. The partition problem involves dividing a given set of integers into two subsets such that the difference between the sums of elements in each subset is minimized. This problem is particularly relevant in situations where resources need to be allocated optimally, such as load balancing, scheduling, and data distribution. The minimum partition algorithm aims to find the best possible partition of the input set by minimizing the difference between the sums of the two subsets. One common approach to solving the minimum partition problem is through dynamic programming. This method involves constructing a table that records solutions to subproblems, which can then be combined to obtain the optimal solution for the original problem. The algorithm starts by sorting the input set in non-decreasing order and initializing a two-dimensional boolean array that represents whether a certain sum is achievable using the first 'i' elements of the sorted set. By iterating through the input set and filling up the boolean array, the algorithm can determine the range of achievable sums. Once the array is filled, the algorithm searches for the largest sum less than or equal to half of the total sum, which represents the partition point with the minimum difference between the sums of the two subsets. The time complexity of this approach is O(n * sum), where 'n' is the number of elements in the input set and 'sum' is the total sum of the elements.
"""
Partition a set into two subsets such that the difference of subset sums is minimum
"""


def findMin(arr):
    n = len(arr)
    s = sum(arr)

    dp = [[False for x in range(s + 1)] for y in range(n + 1)]

    for i in range(1, n + 1):
        dp[i][0] = True

    for i in range(1, s + 1):
        dp[0][i] = False

    for i in range(1, n + 1):
        for j in range(1, s + 1):
            dp[i][j] = dp[i][j - 1]

            if arr[i - 1] <= j:
                dp[i][j] = dp[i][j] or dp[i - 1][j - arr[i - 1]]

    for j in range(int(s / 2), -1, -1):
        if dp[n][j] is True:
            diff = s - 2 * j
            break

    return diff

LANGUAGE:

DARK MODE: