0

I need an algorithm for checking if an array can be divided into 2, or in general, any number of subarrays (need not be contiguous) such that the sum of all the elements of the array does not exceed a certain number. I believe that it basically has to do something with Dynamic Programming. Here's my code in Python:

def func(array, pile1, pile2, memo={}):
    if len(array) == 1:
        return (array[0] <= pile1 or array[0] <= pile2)

    elif sum(array) <= pile1 or sum(array) <= pile2:
        return True

    elif max(array) > max(pile1, pile2):
        return False

    elif sum(array) > pile1 + pile2:
        return False

    elif (array, pile1, pile2) in memo:
        return memo[(array, pile1, pile2)]

    elif (array, pile2, pile1) in memo:
        return memo[(array, pile2, pile1)]

    else:
        item = array[-1]
        array = array[:-1]

        pos1 = func(array, pile1-item, pile2, memo) if pile1-item >= 0 else False
        pos2 = func(array, pile1, pile2-item, memo) if pile2-item >= 0 else False

        memo[(array, pile1, pile2)] = pos1 or pos2                  

        return memo[(array, pile1, pile2)]

The two piles originally contain the maximum.

I searched on the web and found no such solution. Could you please help me with this?

Thanks.

TheRandomGuy
  • 337
  • 5
  • 20
  • OTTOMH, it seems that you want to split the array in 2 (for the basic case) such that the two sub arrays have items with sum of under some given limit. Why not run through the array summing the items in the array until you hit the given limit, and from the previous index check if the rest also fulfil the condition? In other terms, why not look for an index `i` where the sum of all items before is smaller than the limit, and see if the sum of all items after are also smaller? This is `O(n)`. – shapiro yaacov Jun 27 '16 at 11:02
  • @shapiroyaacov The subarrays might not necessarily be contiguous. For example, let the limit be 4 and the array `[2, 4, 2]`. The algorithm won't work correctly. – TheRandomGuy Jun 27 '16 at 11:04
  • So your question has nothing to do with arrays. You have a bunch of numbers and you need to sort in two s.t. `sum(half_1), sum(half_2) < limit` ? – shapiro yaacov Jun 27 '16 at 11:05
  • @shapiroyaacov Yes! Perhaps the word `set` must be a better choice. – TheRandomGuy Jun 27 '16 at 11:06
  • 1
    I'd have a quick look at https://en.wikipedia.org/wiki/Partition_problem and at http://stackoverflow.com/questions/6597180/divide-an-array-into-two-sets-with-minimal-difference – shapiro yaacov Jun 27 '16 at 11:34
  • How large will pile1 and pile2 be? – zw324 Jun 27 '16 at 11:45
  • @ZiyaoWei About a million. – TheRandomGuy Jun 27 '16 at 11:46
  • Mmm that is a bit large - how many numbers are there? There is a pseudo-polynomial time DP but if the range is large it is very slow. – zw324 Jun 27 '16 at 11:52
  • @ZiyaoWei About a 100. – TheRandomGuy Jun 27 '16 at 12:30
  • 1
    This is NP-hard, so don't expect fast, exact solutions. Reason: the Partition Problem is NP-hard, and any instance of that problem can be easily turned into an instance of your problem, just by setting the "certain number" to half the sum of all elements. – j_random_hacker Jun 27 '16 at 14:58

0 Answers0