0
$\begingroup$

If I have the following array: pieces = {35,15,20,25,30,10} and the time slot is 80 minutes. How do I do the following:
1. Fill the time slot with any pieces for the perfect fit. (In our case: 30,35,15 or 15,25,30,10 etc.) 2. Fill the time slot with the best fit possible with deviation: (Let's say our time slot is 103 minutes and the deviation is +/-20 minutes. So, we are looking for the best fit anywhere in the 83-123 minute range.
3. Is there any optimizations that can be done if pieces array is sorted?

I'm looking for basic CS algorithms and strategies for optimizing runtime or space. I'm not looking for a specific solution to my problem. Instead, I'm interested in the CS topics I need to look into.

I'm able to solve the simplest version of this problem: Find out if 2 pieces for the time slot and return true. Solution: Loop through the array. Create hashtable and check if hashtable contains timeslot-pieces[i] if yes, then return true, if no, then add to hashtable.

$\endgroup$
  • $\begingroup$ This is SUBSET SUM. $\endgroup$ – Yuval Filmus Oct 9 '18 at 0:43
0
$\begingroup$

This is a well known problem in computer science, and can be mentioned as "Find all distinct subset sums in an array". The obvious solution is to generate all subsets which will take O(2^n) time for an array of i elements. Instead, if the sum that you can make is relatively small, you can can use dynamic programming technique to precompute a table which will mark the reached sums. The implementation details of these two ideas can be seen here. Notice that this answers also the second question.

Regarding the third point, whether having a sorted array will allow for further optimizations, the answer is no. If you would've had an applicable greedy solution (taking always the maximum or the minimum element according to some criteria) than it would've been very possible to optimize it somehow, but with simple tests it can be proven that greedy doesn't work in this case. (if it had it would certainly be faster than the dp).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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