For a school assignment I am to create Javacode for the following problem, I would like some tips and help on the pseudocode, not the actual java code. It has to be recursive. Personally, I think it's some kind of variation on the knapsack problem, or weighted interval scheduling. Anyways, this is the problem:
A company behind an operating system supplies security updates via the Internet. At a certain moment in time, a number of updates are in development, and for each update the date when it is ready is known.
Shipping an update incorporates a constant cost, equal for each update, and variable cost, which can differ between updates.
To minimize costs, the company is exploring the possibility of bundling updates. A bundle is a series of updates that is shipped in one go. The constant costs for a bundle is equal to the constant cost of one update, but the variable costs of a bundle are defined as the sum of the variable costs of the updates in it.
Bundling updates can thus decrease the constant costs, but it also has a drawback: postponing all security updates in a bundle until the complete bundle is ready means users are longer at risk. This risk is modelled as an extra cost. Essentially, there is a trade-off between shipping an update directly (with a high sum of constant costs) or postponing and shipping it in a bundle (with a high risk).
Suppose the updates are sorted on the time when they are ready. Assume that when an update is shipped, all updates that were ready earlier are shipped also (in the same bundle or in an earlier bundle). The company would like to know how to bundle updates, so that the total costs of all bundles are minimized.
The following information is given:
- a list of numbered security updates, sorted on the date when they are ready (the updates are indicated by 1,2,. . . ,)
- the constant cost of shipping a bundle
- for each update, the variable cost of shipping it
- for each pair of updates, the cost of postponing all updates from the first update to the second update until the second update is shipped.
Think about how to compute the minimum cost f(k) of sending out all updates 1 up to k.
This can be computed recursively, but make sure you memoize the results of the function calls or your complexity will become exponential.