java - 最小化捆绑更新的成本(反向背包？)

Question

对于一项学校作业，我要为以下问题创建 Java 代码，我想要一些关于伪代码的提示和帮助，不是实际的 java 代码。它必须是递归的。就个人而言，我认为这是背包问题或加权间隔调度的某种变体。无论如何，这就是问题所在:

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.

给出以下信息:

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

Answer 1

考虑如何计算发送所有更新 1 到 k 的最小成本 f(k)。

这可以递归计算，但请确保记住函数调用的结果，否则您的复杂性将呈指数级增长。