-1
$\begingroup$

Take the following array of integers:

[60, 45, 30, 45, 45, 5, 60, 45, 30, 30, 45, 60, 60, 45, 30, 30, 60, 30, 30]

They need to be sorted into pairs of sub-arrays. The first sub-array in each pair must total at most 180, and the second must total at most 240.

How would you find the right combinations of elements so that no elements are remaining after all pairs have been created? I'm told that it is possible with this data set.

Improve this question
$\endgroup$
5
  • 2
    $\begingroup$ What did you try? Where did you get stuck? $\endgroup$
    – David Richerby
    Commented Aug 31, 2014 at 7:12
  • $\begingroup$ Are you looking for one solution, or a general method to solve this kind of problem? $\endgroup$
    – Florian F
    Commented Aug 31, 2014 at 21:26
  • $\begingroup$ There must be a typo. An array of 180 plus an array of 240 sums to 420. The sum of your items is 785, not a multiple of 420. And all elements are multiple of 15, except for the 5 which is not. You can not use it in a subarray that sums to 180 or 240. $\endgroup$
    – Florian F
    Commented Aug 31, 2014 at 21:35
  • 1
    $\begingroup$ I have integrated your edit into the actual question, since future visitors will not care about the previous wrong version. $\endgroup$
    – FrankW
    Commented Sep 1, 2014 at 7:21
  • 1
    $\begingroup$ This problem does indeed seem to admit trivial solutions if there are not too many big elements, and none at all otherwise. Are there no other restrictions, such as minimising the number of pairs in the result? $\endgroup$
    – Raphael
    Commented Sep 1, 2014 at 10:58

1 Answer 1

Reset to default
1
$\begingroup$

This is trivial: Since all elements are less than 90, you can create one sub-array with 2 elements and 17 sub-arrays with a single element each and pair them in any way you like.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.