Finding the maximum possible size of S, where S is a set of pairwise-disjoint subsets of the list, and every element of S sums to k
-
05-11-2019 - |
문제
Say I had a list of numbers in the range of 1-20 for example: [5, 16, 17, 3, 2, 14, 4, 9, 11, 19], and an integer k (let's say k = 40)
How would I find the maximum possible size of S, where S is a set of pairwise-disjoint subsets of the list, and every element of S sums to k?
I believe this algorithm is NP complete.
Just think of the problem as a bin packing algorithm but instead of saying that the total value of items in the bin must not exceed the bin's capcacity, I am saying that the total value of items in the bin must be exactly equal to the bin's capacity. Also, we are trying to maximise the number of bins.
Example scenario:
Say I have a list: [1, 2, 2, 3, 5, 6, 5] and k=7, then some example values of S would be:
[(3+2+2), (6+1)] - 5 and 5 left over
[(5+2), (5+2), (6+1)] - 3 left over
As you can see, the second solution is optimal because it produces 3 partitions rather than 2.
올바른 솔루션이 없습니다