From Newsgroup: comp.programming

Good day, lord.
On Thursday, January 26, 2023 at 11:00:35 PM UTC+2, Richard Heathfield wrote:

On 26/01/2023 7:50 pm, Stefan Ram wrote:

The same book also gave another problem that could supposedly be
solved using dynamic programming: In a restaurant you are shown
five dishes in a sequence, and you can choose one to eat. You are
shown only one dish at a time and do not know which dish will be
shown next. Once you accept or reject a dish, you cannot go back on
your decision. If you do not choose any of the first four dishes,
this means that you would inevitably eat the last one. How should
you proceed to maximize the probability of getting the best dish?

The solution given in the book begins by explaining that you
assign a quality score between 0 and 1 to each dish you see.
So the question is how to proceed to maximize the probability
of eating a dish with a quality score as high as possible . . .

0123456789 spoiler space
0123456789 spoiler spac
0123456789 spoiler spa
0123456789 spoiler sp
0123456789 spoiler s
0123456789 spoiler
0123456789 spoiler
0123456789 spoile
0123456789 spoil
0123456789 spoi
0123456789 spo
0123456789 sp
0123456789 s
0123456789
0123456789
012345678
01234567
0123456
012345
01234
0123
012
01

Reject (but score) the first two dishes, and then accept the
first dish that scores better than any you have yet seen (or the
last if you must and are very hungry).

This algorithm will pick the best of five dishes about seven
times in twenty visits.

--
Richard Heathfield
Email: rjh at cpax dot org dot uk
"Usenet is a strange place" - dmr 29 July 1999
Sig line 4 vacant - apply within

--- Synchronet 3.20a-Linux NewsLink 1.114