1
$\begingroup$

Title of the question pretty much summarises the question. Here is a concrete example of what I'm trying to achieve with no success. Let's say we have a sorted list (but sorted is not a requirement) L = [1,3,20,100,150,200,260] and K = 260. I need a function f(L,K) which given this list and K will return a list B = [[1,3,20,200],[100,150],[260]]. As you see if we just group elements in their sorting order with their sum <= K like this: [[1,3,20,100], [150], [200], [260]] we will have 4 subarrays but it's possible to have 3. This algorithm may be useful for instance to make a compact linear stack layout of some UI elements of different lengths with min number of lines of those elements.

UPD. I decided to remove a word "efficient" from the question because this looks like an NP-hard problem. To be clear I need more or less optimal but correct solution. Numbers will not be large because I'm talking about this problem in the context of practical task (efficient UI layout) that's why K and list elements will be a small numbers in the range [0, ..., ~1000]. I put a label "dynamic programming" because I think that this problem may be solved with dynamic programming approach and as was mentioned in the first comment is related to bin packing problem.

$\endgroup$
  • 1
    $\begingroup$ Start exploring solutions to bin packing problem $\endgroup$ – nvartolomei Dec 14 '17 at 12:25
  • $\begingroup$ Care to share your thoughts about "the greedy approach"? $\endgroup$ – greybeard Dec 14 '17 at 13:13
  • $\begingroup$ Your question is NP-hard by an easy reduction from PARTITION. That doesn't mean you can't solve it in practice if the numbers are small. $\endgroup$ – Yuval Filmus Dec 14 '17 at 14:24
  • $\begingroup$ @YuvalFilmus Could you please elaborate more on "by an easy reduction from PARTITION". I'm currently stuck and can't come up with just a right algorithm. I'm not even talking about efficiency. $\endgroup$ – MainstreamDeveloper00 Dec 14 '17 at 15:49
  • $\begingroup$ @greybeard I don't have any thoughts about "greedy approach" and didn't even mentioned this in my question. Could you please tell what did you mean? I put a label "dynamic programming" because I have a feeling that this problem may be solved with dynamic programming approach and as was mentioned in the first comment is related to bin packing and knapsack problems. $\endgroup$ – MainstreamDeveloper00 Dec 14 '17 at 15:53

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.