Solution to POJ 1018

The problem is on here↗.

Analysis #

There are n group of devices. We should take one and only one device from any group.

Firstly I think it is another Dynamic Programming↗ problem, because what I would choose in each group depends on what I already took in before groups. However, it is not. Because what device I take now would affect the result before. For example, if I took a device with a very low bandwidth, the result before might not be optimal then. If I want to use Dynamic Programming, I have to say, when I already take several devices to make the total price rise to P and bandwidth limited to B, I would choose a optimal device in current group together with the optimal devices I choose before under new limitation P’ and B’. That’s too much complex. What’s worse, the combination of P would be very very large. Under the worst case, it would be $\prod_{0< i \leq n} m_i \leq 100^{100}$.

Obviously, we cannot use Dynamic Programming to solve this problem. What make it not is we need to judge the optimal with B/P, which depends on both B and P, and the B is the minimum of the bandwidths which means it depends on all possible groups.

However, we now the possible final bandwidths are very limited, with no more than the count of all devices which is $\sum_{0 < i\leq n} m_i \leq 10000$. If we fix the final bandwidth, the problem would turn to find the minimum total price P, which is a very simple problem.

Solution #

1. Enumerate all possible bandwidths.
2. For each possible bandwidth, find the minimum total price P.
3. Find the maximum B/P for each optimal P and B.

In the second step, we can follow these steps.

1. Sort devices in each group by its bandwidth. (Do only once, hence should be done before second step above.)
2. Find the slice of each group whose bandwidth all be equal or greater than specified bandwidth B.
3. Find the minimum price P in each sliced group.
4. Sum the total price.

Code is here.