In this lesson, we will be talking about both false solutions.

Such solutions are usually slow but they're clearly correct,

and for this reason,

can be useful for investigating a problem and debugging solutions.

Before implementing an algorithm,

it makes sense to first convince yourself that the algorithm is correct.

At the same time, during competitions,

time is limited hence coming up with a formal proof is usually an unaffordable action.

For this reason in many cases,

one ends up with an intuitive idea instead of a formal proof of its correctness.

But often intuitive solutions do not work.

It'll be good to have an approach with

a guaranteed success where you don't have to rely on your intuition.

In this lesson, we will consider the so-called brute force solutions.

Such algorithms solve a problem in a straightforward way.

They just go through all possible candidates' solutions.

The resulting algorithm is clearly correct,

though in many cases,

it is going to be too slow.

Still, such solution is useful for

debugging other solutions and for investigating the problem.

To illustrate the approach,

consider the following TOY problem.

Given a list of digits,

write them on the blackboard in

such order that the resulting number will be the largest possible.

For example, the largest number that can be composed out of digits five,

seven and three, is 753.

Do you see how to solve this problem for any list of digits?

Indeed, the solution is to order digits from the largest one to the smallest.

Here the first solution you come up with turns out to be correct,

but it's not always the case.

Consider another problem.

A robber breaks into a shop and finds more loot than his bag fits.

How can he decide what to take?

More formally, given the information about items in the shop

namely their weights and costs as well as the capacity of robber's bag.

Can you tell what items should the robber take in order to maximize his profit?

The best items are the most expensive but not very heavy ones.

It is natural to consider cost-weight ratio as goodness or utility of an item.

Items with large utility seem to be better to take.

Hence, lets put items in the backpack,

one by one in the order of decreasing utility.

That's a very natural approach,

which is probably would be used in real life.

Unfortunately, it doesn't work.

Let's see that on an example.

Here we have three items,

the first one costs two dollars and weighs three kilograms.

The second one costs three dollars and weighs two kilograms.

The third one costs six dollars and weighs five kilograms.

The weight limit is five kilograms.

The second item is the best one in the sense of utility.

Let's put it in the backpack.

Among the remaining items,

the second one is the best,

but it doesn't fit in the weight limit.

So, we are left with the first item.

Let's put it into the backpack.

We got five dollar worth items using our approach.

But is it the best solution? Well, No.

The largest item itself could have done better,

thus a solution that seemed to be correct turned out to be wrong.

How to distinguish between a correct solution and a wrong one.

Note that for the robber's problem,

we were just given a counter example for our erroneous solution.

In many cases, finding such an example is tricky.

Moreover, for some problems it is already trickier to

find a solution even for simple cases from the problem statement.

Hence, it would be useful to have a solution that is one hundred percent correct.

In the next video, we will be developing such solutions.