Computer Science Asked by RAS on September 18, 2020

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.

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).

Answered by NiVeR on September 18, 2020

Get help from others!

Recent Questions

- How can I transform graph image into a tikzpicture LaTeX code?
- How Do I Get The Ifruit App Off Of Gta 5 / Grand Theft Auto 5
- Iv’e designed a space elevator using a series of lasers. do you know anybody i could submit the designs too that could manufacture the concept and put it to use
- Need help finding a book. Female OP protagonist, magic
- Why is the WWF pending games (“Your turn”) area replaced w/ a column of “Bonus & Reward”gift boxes?

Recent Answers

- haakon.io on Why fry rice before boiling?
- Peter Machado on Why fry rice before boiling?
- Lex on Does Google Analytics track 404 page responses as valid page views?
- Joshua Engel on Why fry rice before boiling?
- Jon Church on Why fry rice before boiling?

© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP