Geek Answers Handbook

Changing the knapsack (or tiling) algorithm

I have a problem:

A queue of N elements is set, each of which has a weight and a queue of containers K. And we need to divide the objects into containers in the order in which they were. For example, the very first element can go only to the first container, the second to the first or second, but not to the third (otherwise the second container will not have any elements).

I need to create and implement an algorithm that makes a kind of uniform distribution, so the heaviest container should be as light as possible; to count the number of containers with that weight.

I guess this is some kind of variation on the 3-split problem or the backpack. I have already implemented one possible solution for distribution using dynamic programming and tried to get the score from the table used in it. But it was not efficient enough (too expensive amount of memory), and the algorithm for obtaining the number of containers was incorrect.

Can someone please explain which algorithm is the solution to this problem?

+4
source share
1 answer

Thus, the OP problem as a whole can be solved using the DP algorithm given in this question . I will repeat the essence of this here for completeness:

, d [i] [j] , s [1],..., s [i] j . :

  • d [0] [j] = 0 j
  • d [i] [1] = Sum (s [1],..., s [i]) i
  • d [i] [j] = min (max (d [it] [j-1], Sum (s [i-t + 1],..., s [i]) 1 <= <= )

O (NK), . , (3): d[_][j] d[_][j-1]. , d[_][j], , d[_][j-1], d[_][j+1], .

d[0][j] , . , , , O (N) - d[i][1], O (N), j-1 - O (N), j - , . : O (N).

Edit: , , OP , . , w[i][j] i,j th, c[i][j] - , . :

  • c[0][j] = j w[0][j] = 0 j
  • c[i][1] = 1 w[i][1] = Sum(s[1], .., s[i]) i
  • u t, pt (3) .
    • d[i-u][j-1] > Sum(s[i-u+1], .., s[i]):
      • c[i][j] = c[i-u][j-1] w[i][j] = w[i-u][j-1]
      • j th Sum(s[i-u+1], .., s[i] , 1, .., j-1, d[i-u][j-1].
    • d[i-u][j-1] < Sum(s[i-u+1], .., s[i]):
      • c[i][j] = 1 w[i][j] = Sum(s[i-u+1], .., s[i])
      • j th s[i-u+1], .., s[i] - .
    • If d[i-u][j-1] == Sum(s[i-u+1], .., s[i]):
      • c[i][j] = c[i-u][j-1]+1 w[i][j] = d[i-u][j-1]
      • j th , .

, O(N), O(N) .

+1

More articles:


All Articles