ВОРОТА | ВОРОТА КС 2021 | Набор 1 | Вопрос 50
Опубликовано: 7 Октября, 2022
Определим Rn как максимальную сумму, полученную путем разрезания стержня длиной n метров на один или несколько кусков целочисленной длины и их продажи. Для i>0 пусть p[i] обозначает цену продажи стержня длиной i метров. Рассмотрим массив цен:
p[1]=1, p[2]=5, p[3]=8, p[4]=9, p[5]=10, p[6]=17, p[7]=18
Какое из следующих утверждений верно в отношении R7?
(А) R7=18
(Б) R7=19
(C) R7 достигается тремя различными решениями
(D) R7 не может быть достигнуто решением, состоящим из трех частей
Ответ: (А) (С)
Объяснение: По приведенным данным,
| Количество штук | Возможная максимальная прибыль с комбинацией размера стержня |
| 7 | 7 (1, 1, 1, 1, 1, 1, 1) |
| 6 | 10 (2, 1, 1, 1, 1, 1) |
| 5 | 13 (2, 2, 1, 1, 1) |
| 4 | 16 (2, 2, 2, 1) |
| 3 | 18 (2, 2, 3) |
| 2 | 18 (6, 1) |
| 1 | 18 (7) |
Следовательно,
Варианты (А) и (С) верны.
Обратитесь – Резка стержня | DP-13 и решение — https://ide.geeksforgeeks.org/lbBeyHa3xd
Тест на этот вопрос