Variation of knapsack (or partition) algorithm

Question

the question I have a problem is as follows:

Given a queue of N items, each with a weight, and the queue of K containers. And we need to partition the items to the containers in the order they came. For example, the very first item can only go to the first container, the second one can go to either the first or the second but not the third (otherwise the second container won't have any items).

I need to create and implement an algorithm that make some kind of uniform distribution, so the heaviest container must be as lightweight as it can; to give count of containers with such weight.

I suppose it is some variation of 3-partition or knapsack problem. I have already implemented one possible solution for distribution using dynamic programming and tried to get count from the table used in it. But it was not effective enough (too much memory expensive), and algorithm of getting the amount of containers wasn't correct.

Can someone explain, please, which algorithm is solution for this problem?

Answer 1

So the OP's problem in general can be solved by the DP algorithm given in this question. I'll repeat the crux of it here for completeness:

Suppose d[i][j] is solution of the problem when we have items s[1], .., s[i] and j containers. Then:

1. d[0][j] = 0 for each j
2. d[i][1] = Sum(s[1], ..., s[i]) for each i
3. d[i][j] = min(max(d[i-t][j-1], Sum(s[i-t+1], ..., s[i]) over all 1<=t<=i)

However, the naive implementation consumes O(NK) space, which is too much. Fortunately, look at (3): d[_][j]'s value depends only on d[_][j-1]. This means that once we're done computing all d[_][j], we can use the space we were using to store d[_][j-1] to instead store the values of d[_][j+1] we're about to compute.

Since the values d[0][j] are all zero, we don't need to store those either. Hence the only arrays we need to store are the O(N)-sized d[i][1], the O(N)-sized array that holds the result from the j-1th iteration, and the O(N)-sized array that holds the results from the jth iteration we're currently computing. Total: O(N).

Edit: So first time round, I didn't actually answer the OP's question about how to count the number of containers at max weight. Suppose w[i][j] holds the max weight of the i,jth problem, and c[i][j] is the number of containers which match that max weight. Then:

1. c[0][j] = j and w[0][j] = 0 for each j
2. c[i][1] = 1 and w[i][1] = Sum(s[1], .., s[i]) for each i
3. Let u be equal to the t chosen in pt (3) above.
   • If d[i-u][j-1] > Sum(s[i-u+1], .., s[i]):
     • then c[i][j] = c[i-u][j-1] and w[i][j] = w[i-u][j-1]
     • because the jth container with weight Sum(s[i-u+1], .., s[i] is lighter than the heaviest container out of containers 1, .., j-1, which has weight d[i-u][j-1].
   • If d[i-u][j-1] < Sum(s[i-u+1], .., s[i]):
     • then c[i][j] = 1 and w[i][j] = Sum(s[i-u+1], .., s[i])
     • because the jth container with items s[i-u+1], .., s[i] is the new heaviest container.
   • If If d[i-u][j-1] == Sum(s[i-u+1], .., s[i]):
     • then c[i][j] = c[i-u][j-1]+1 and w[i][j] = d[i-u][j-1]
     • because the jth container is the same weight as the previous heaviest container.

Again, we only need to use a constant number of O(N) sized arrays, for O(N) time overall.