I stumbled upon the Dynamic Programming Paradigm early in my corporate accounting career while working on budget allocations. It was my first time ever budget planning on a corporate level and I needed an efficient way to calculate various combinations of allocations across different departments and projects—essentially, my subset sums. After coming home that night, unsure where to begin, I researched algorithms to help me find optimal solutions using the existing budgets. During my exploration, I came across Richard Bellman's work on the Dynamic Programming Paradigm. This new approach enabled me to effectively address my initial challenge. Combined with regression analysis, it has proven invaluable in optimizing budget allocations!

You may be asking, "So how does it work?"

Well, the Dynamic Programming approach efficiently solves the subset sum problem by breaking it into smaller overlapping subproblems and storing intermediate results to avoid redundant calculations. I know there can be various approaches to this but through adjustments and A LOT of trial and error, I find that this particular approach is useful in accounting for budget allocation and resource distribution, I even used it a few times to refresh my eyes when reconciling financial statements.

One thing I could have done better is build this with a GUI, but I’ll save that for a future project. It's still quite simple to use for individuals with no programming background; all you need to do is adjust the number set (the part of the code where it says "numbers = [") & target (the part of the code where it says "target =") to the numbers you have and then run this through a compiler and Tadaah! It'll print out the solution to your problem, or not. LOL! Feel free to try at your own risk and let me know how it goes for you.

Check out the example I set below with some randomly generated numbers.

def find_subset_sum(numbers, target, tolerance=1e-2):
    # Scale the target and numbers for better precision with integers
    scale = 100
    scaled_numbers = [int(num * scale) for num in numbers]
    scaled_target = int(target * scale)

    dp = [None] * (scaled_target + 1)
    dp[0] = []

    for num in scaled_numbers:
        for i in range(scaled_target, num - 1, -1):
            if dp[i - num] is not None:
                dp[i] = dp[i - num] + [num / scale]

    result = dp[scaled_target]
    return result if result is not None else []

# Example usage
numbers = [
        256.28, 409.25, 4945.26, 177.00,
        818.40, 191.00, 871.00, 205.00,
        804.99, 125.00, 786.00, 1768.00,
        568.55, 992.00, 110.00, 992.00,
        2839.00, 837.60, 112.75, 106.34,
        1611.76, 2410.83, 1488.00, 999.16,
        999.65, 5850.00, 5850.00, 5850.00
]
target = 3442.60

result = find_subset_sum(numbers, target)
print(f"Subset that sums up to {target}: {result}")

# This is licensed under the GNU General Public License. Download license for more details.

Here’s a deeper breakdown to help you better understand it.

The Function: The find_subset_sum function is designed to find a combination of numbers that add up to a specific target value, taking into account a small tolerance to manage any floating-point precision issues.

Scale Values: We use a scaling factor, set to 100, to convert floating-point numbers into whole numbers. This makes our calculations more precise.

Scale Numbers: Each number in the list is multiplied by the scaling factor and converted to an integer. This helps in handling floating-point numbers more accurately.

Scale Target: Similarly, the target value is also scaled to match the format of the numbers for consistency in calculations.

Initialize DP Array: We create a list called dp where each position represents a possible sum up to our scaled target. Initially, all entries are set to None, which means we haven’t found any sums yet.

Set Base Case: We set dp[0] to an empty list, signifying that a sum of zero can be achieved with no numbers.

Iterate Through Numbers: We loop through each number in the scaled list to process them.

Update DP Array: We check each possible sum from our target down to the current number, making sure we use each number only once. If a valid subset that adds up to a certain sum is found, we update our list to include the current number, reverting it back to its original scale.

Check and Update: We verify if we can form the current sum by checking if the previous sum (i - num) has a valid subset. If it does, we update our list to include the current number.

Get Result: We retrieve the subset from our list that adds up to the scaled target, if it exists.

Return Result: If a valid subset is found, we return it; otherwise, we return an empty list.

Define Numbers and Target: We set up a list of numbers and specify the target sum we want to achieve.

Call Function: We invoke the find_subset_sum function with our numbers and target to find the subset.

Print Result: Finally, we display the subset that adds up to the target sum, if such a subset is found.