1
\$\begingroup\$

Note - I am not sure whether this question belongs to stackoverflow or CSE stackexchange or here

Problem:

Given a list Lconsisting of not necessarily unique non-negative integers, find the minimum number of subset with maximum sum k(given) in which it can be divided such that: each subset shouldn't contain consecutive elements from the list*.

(*): I can see an obvious ambiguity:
Q: If there is 3 4, is the restriction is on all 3 or just the adjacent three?

A: Just on adjacent 3.

Examples:


1. L = [2, 1, 1, 2], k = 2 => 4 

Explanation: First set can take 0th index element
             second set can take 1st index element and similarly third and fourth can take 2nd and 3rd index element respectively

Here, you can see that k is working as a bottleneck

More examples:

L = [2, 4, 1, 0] k = 8 => 2

L = [3, 2, 3, 0, 0] k = 5 => 3

This seems to have some features of dynamic programming problems, so I went for dynamic programming and wrote the following recursive code:

from functools import lru_cache
def min_count(L, k):
    '''
    index - stores the current state's index
    sets - this stores information of already stored sets:
            It is tuple of tuple, 
                In each tuple:
                    First element - index of last stored element
                    Second element - stores the sum of current set
    k - It is limit|capacity of each subset(same as the one given in arugment)

    '''
    @lru_cache(maxsize=None)
    def recurse(index, sets, k):
        #If control reaches to the end of the list
        if index == len(L):
            return len(sets)

        #In case the current indexes is zero
        if L[index] == 0:

            #If this is the last index, then
            if index + 1 == len(L):
                return len(sets)
            return recurse(index + 1, sets, k)


        '''

        The job of this for loop is iterate all of the stored sets:
            And if that's capable of storing further, then add current index
            to it, and recurse
        '''
        m = 1e10
        for i, j in sets:
            if i - index < -1 and j + L[index] <= k:
                if index + 1 == len(sets):
                    return len(sets)
                m = min(m, recurse(index + 1,tuple(_ if _ != (i, j) else (index, j + L[index]) for _ in sets) , k))
        


        m = min(m, recurse(index + 1, sets + ((index, L[index]), ), k))
        return m


    return recurse(0, (), k)

The problem is that this code works, but is very slow(the expected time complexity must be lower than O(n^2)).

How can I make it fast?

\$\endgroup\$
2
  • \$\begingroup\$ when would more than two subsets be required? Taking every other element should be non consecutive \$\endgroup\$ Jan 7 '21 at 16:55
  • \$\begingroup\$ Example: L = [2, 2, 2, 2, 2] with k = 2 \$\endgroup\$
    – u_sre
    Jan 7 '21 at 17:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.