Условие задания:
30 Б.
Странствующий рыцарь как-то вызвал на бой живущего рядом дракона. Долгой была битва, и победил в ней рыцарь... И только он занёс меч, чтобы последним ударом срубить мерзкому чудовищу голову, как вдруг услышал:
- Пожалей меня, добрый рыцарь! Я с тобой расплачусь!
- А как?
- Я тебе отдам четыре…нет, три любых драгоценных камня из моей сокровищницы!
Рыцарь посмотрел на свой заплатанный плащ, на прохудившиеся сапоги — и согласился. Но в последний момент в драконе взыграла природная жадность, и он сказал:
- Но суммарная стоимость камней не должна быть слишком большой! Я ценю свою жизнь в M золотых! Так что суммарная стоимость камней не должна превысить M!
Задумался рыцарь…Считать — не мечом махать! Ведь каждый камень имеет свою цену, а подобрать камни так, чтобы их суммарная стоимость не превысила оговоренной суммы, но была максимальной, непросто. Помогите ему!
- Пожалей меня, добрый рыцарь! Я с тобой расплачусь!
- А как?
- Я тебе отдам четыре…нет, три любых драгоценных камня из моей сокровищницы!
Рыцарь посмотрел на свой заплатанный плащ, на прохудившиеся сапоги — и согласился. Но в последний момент в драконе взыграла природная жадность, и он сказал:
- Но суммарная стоимость камней не должна быть слишком большой! Я ценю свою жизнь в M золотых! Так что суммарная стоимость камней не должна превысить M!
Задумался рыцарь…Считать — не мечом махать! Ведь каждый камень имеет свою цену, а подобрать камни так, чтобы их суммарная стоимость не превысила оговоренной суммы, но была максимальной, непросто. Помогите ему!
Список стоимостей камней дракона:
51 | 82 | 20 | 20 | 57 |
22 | 51 | 51 | 26 | 62 |
44 | 22 | 46 | 51 | 31 |
76 | 62 | 35 | 86 | 60 |
28 | 75 | 42 | 68 | 62 |
84 | 71 | 84 | 93 | 39 |
66 | 20 | 93 | 51 | 30 |
62 | 62 | 22 | 62 | 79 |
91 | 42 | 33 | 46 | 77 |
71 | 22 | 28 | 62 | 44 |
Лучшая сумма стоимостей камней, которую может получить рыцарь (не больше трёх камней!), не превышающая \(M =\) 267: