Partition Problem - 2 subsets of equal sum, as closely as possible - tutorial and source code
HTML-код
- Опубликовано: 5 сен 2024
- Partition a set of positive integers into two subsets such that the sum of the numbers in each subset adds up to the same amount, as closely as possible. This is an NP-complete problem, dubbed as “the easiest hard problem”. First, we’ll develop a recursive solution with a source code walk through. And then we’ll discuss a completely different solution that uses dynamic programming.
For this problem, we are going to assume that we are dealing with multisets. Meaning, the sets are not restricted to have unique numbers. Therefore, we’ll use arrays to be able to store duplicate numbers.
Partition Problem solved using recursion, source code implementation in Java that creates two partitions:
bitbucket.org/...
Dynamic Programming solution, explained in "0/1 Knapsack Problem" tutorial, can be directly applied to solve this problem:
• 0/1 Knapsack Problem U...
Source code for 01 Knapsack problem using dynamic programming implementation in Java:
bitbucket.org/...
Further reading: en.wikipedia.o...
Written and narrated by Andre Violentyev