1
$\begingroup$

I have two types of items, $i_1$ and $i_2$. $i_1$ items can be used at most $50$ times and $i_2$ items can be used at most $120$ times. I have $7000$ items $i_1$ and $800$ items $i_2$.

Each item $i\in \{1,\dots,7800\}$ has a duration $0$ $< d_i\le$ $1$ second. I have $365$ days. I can use each item only once to fill a day, and, as previously said, each item can fill several days. A day is considered filled when at least one hour is filled. How many days at most can I fill as a function of the vector $d$?


A trivial bound on the solution of this problem is $365$ days. Another bound is to suppose that every item last 1 second which leads to a solution of $123$ days. Can you do better?

$\endgroup$
4
  • $\begingroup$ Do the first 7000 indices refer to the $i_1$ items? I presume the the function will depend heavily on which indices are $i_1$ and which are $i_2$. $\endgroup$
    – hexomino
    Feb 19 at 15:47
  • $\begingroup$ @hexomino Yes, the first 7000 indices are the $i_1$ items and the 7001 to 7800 are the $i_2$ items, thanks for spotting it! $\endgroup$
    – JKHA
    Feb 19 at 15:50
  • $\begingroup$ Do you really want the maximum number of days as a function of $d$, or do you instead just want to find the best $d$? $\endgroup$
    – RobPratt
    Feb 19 at 16:25
  • $\begingroup$ @RobPratt, nope, the vector $d$ is an input parameter, I want the maximum number of days as a function of the input $d$. $\endgroup$
    – JKHA
    Feb 19 at 16:29

1 Answer 1

1
$\begingroup$

It seems to me there is a knapsack-like quality that would make perfect optimization difficult. (For example, if $d_i$ are rational, asking if it is possible to fill exactly one hour in a particular day is an instance of the subset sum problem.) I will mostly ignore this part of the problem.

If we stop using items after filling an hour, we might have a little time left over, but only the remaining duration of the last-used item -- less than a second. I resign myself to losing this time. (This is part of what I mean by ignoring the knapsack part of the problem.) Also, there may be some extra time at the end that doesn't add up to a full hour. Obviously, we can never do anything with this.

There is an obvious upper bound of using all the time from all the items. The only other way we can fall short of this bound is if the remaining time is concentrated in a few items so we can't use enough in the same day. For example, the 50-use items could be exhausted, and the remaining uses of the 120-use items then couldn't be used (as they can only give 800 seconds per day). (I would say this includes the degenerate inputs where using all the items doesn't give a full hour; but those are trivial.)

So, each day we order the items from most remaining uses to least. Then, we use them in order until we have reached an hour for the day. (Then we reorder based on remaining uses for the next day.) In practice this is generally the same as using all the 120-use items each day, and using the 50-use in order (remembering the index from day to day) and looping. But, if the 120-use items catch up in uses to the 50-use items, then they are basically all treated the same at that point. In any event, all the 50-use items stay within one remaining use of all the others, and if the 120-use items catch up, then all the items stay within one remaining use. If items are within one remaining use, then none are exhausted except when we can use all the remaining of those items (or have already used them today).

One possibility is that the 120-use items never catch up in remaining uses to the 50-use items. In this case, the 50-use items will all be used up. It won't have been possible to have gotten any more time out of the 120-use items because we already used them all every day (except if maybe we could have gotten one more day out of the time I resigned myself to losing).

On the other hand, if the 120-use items do catch up, then we end up being able to use all the time from all the items. The only time we lost is time we resigned ourselves to losing (which is not very much).

If you want to attack the knapsack part of the problem, you could obviously tie-break among items with the same number of remaining uses by choosing them to minimize the excess for the day -- this doesn't really change anything. But, it is not clear that this is always optimal (almost certainly I think it isn't). It could be that more excess one day leads to even less excess another day. Or, maybe it is not optimal to use an item with the largest number of remaining uses -- but balancing competing concerns of minimizing the daily excess versus the needs of future days seems like it gets very complicated.

If you want a formula, subtract the sum of the 120-use durations from 3601 seconds (3601 assuming the worst case of losing a second every hour; or we could be optimistic and use 3600; we should land in-between). Divide the total time in the 50-use items by this number. If the quotient is less than 120, then that's how many days we can fill, and we are in the first case where the 120-use items don't catch up (or not until the very end). Otherwise, we can use all the time, so divide all the time in all the items by 3601. (You also might check for the degenerate case where no days can be filled.)

$$f(d) \geq \begin{cases} 0 & \sum_i d_i < 3600 \\ \lfloor \frac{50 \sum_{i\leq 7000} d_i}{3601-\sum_{i>7000} d_i} \rfloor & \sum_i d_i \geq 3600 \text{ and } \frac{50 \sum_{i\leq7000} d_i}{3601-\sum_{i>7000} d_i} < 120 \\ \lfloor \frac{50 \sum_{i\leq 7000} d_i + 120 \sum_{i>7000} d_i}{3601} \rfloor & \text{otherwise}\end{cases}$$

$\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.