I have this problem where I need to design a greedy algorithm. The problem is as follows:

A chocolate factory owns $n$ stores, which are connected by a single road. Each store has a limited supply $c_i$ of chocolates. Furthermore, the factory would like to have the same amount of chocolate in each store. Therefore, they hired a truck driver to haul chocolates between the stores, but the driver eats two chocolate bars for each kilometer he drives.

Calculate the largest amount of chocolate $C$ they can have at each store.

Input: The position $p_i$ and chocolate supply $c_i$ of each store. The positions are in increasing sorted order.

Output: The largest amount $C$, such that each store can have a chocolate supply of at least $C$ after the truck driver has hauled between the stores.

I have a problem with identifying the greedy choice property for the problem. So far I came up with the following:

The greedy choice can be the minimum arithmetic mean of two neighbouring stores minus the delivery cost divided by $C$, but it has to be larger or equal to 1. I came up with the following equation: $$\min\{\frac{\frac{1}{n} \cdot (c_i + c_{i_{neighbour}} - delivery_{cost})}{C}\}$$

Where the delivery cost is $2\cdot |p_i - p_{i-1}|$.

I am not sure if this approach is the right one. I am open for hints and partial solutions.

没有正确的解决方案

许可以下: CC-BY-SA归因
不隶属于 cs.stackexchange
scroll top