Shops problem

Using brute strength on a one-dimensional array

Consider a row of shops. A company wishes to purchase a single contiguous segment of neighbouring shops in the row. The company has access to the yearly profits of each shop; the profits may sometimes be negative (i.e., a loss). The problem is to find the maximum profit available to the company.

To approach this problem, consideration of some examples will serve to highlight the issues involved in developing a solution.

Example 1

Clearly, the maximum profit available here is £17,000, which comes from buying all three shops. However, there may be times when buying all the shops is not the best approach.

Example 2

Here, the best profit is £10,000, which comes from buying only the first shop and ignoring the others. The problem is complicated when we want to buy a shop to make up a contiguous row, even though its individual contribution to the overall profit is negative. Consider example 3.

Example 3

We could choose shop 1 because of its profits of £6,000. However, shop 3 makes a good profit and we would like to buy this one as well, but we cannot do this directly because shops 1 and 3 do not make up a contiguous (unbroken) group. In this case it is worth taking on shop 2 as well despite its loss. This is because the total profit from the three shops combined is £9,000 with the loss from shop 2 being compensated by the additional profit from including shops 3 in the chain.

The approach to solve this problem is quite straightforward: we list each possible group of shops, calculate the profit from each group and select the highest. The table below shows all possible groups when there are four shops in a row.

Note that each group can be defined by its starting and finishing shops. These groups can thus be listed thus:

Refer to the program outline (click here to view, right click here and choose 'Save as' to download) and write a program to analyse the shop profit data provided and, hence, obtain the screen output shown below.

Hints

Note that the shop numbering shown above runs from 1 to 4, while the shop array is numbered 0 to 3. Obtain the correct numbering by adding 1 to the shop counts output.

This type of algorithm is known as the brute strength approach. As the name implies, this is not a particularly 'clever' method, relying on some subtle technique to ensure an efficient algorithm. Rather, it gets the correct answer by analysing all possible options and choosing the best. There is a downside to this: although problems can be solved using brute strength alone, the time required for their solution grows exponentially as the size of the data increases. For such problems, even modest data sizes make the solution impractical in a reasonable time, however fast the processor on which the program runs.