Note - I am not sure whether this question belongs to stackoverflow or CSE stackexchange or here
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
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
How can I make it fast?