Рубрики

ВОРОТА | GATE CS 2010 | Вопрос 65

Вес последовательности а 0, 1, …, н-1 действительных чисел определяется как 0 + 1/2 + … + а а-1/2 п-1. Подпоследовательность последовательности получается путем удаления некоторых элементов из последовательности, сохраняя порядок остальных элементов таким же. Обозначим через X максимально возможный вес подпоследовательности a 0 , a 1 ,…, a n-1, а Y — максимально возможный вес подпоследовательности a 1 , a 2 ,…, a n-1 . Тогда X равно
(A) max (Y, a0 + Y)
(B) max (Y, a0 + Y / 2)
(C) max (Y, a0 + 2Y)
(D) a0 + Y / 2

Ответ: (Б)
Пояснение: Используя понятия динамического программирования, чтобы найти максимально возможный вес подпоследовательности X, у нас будет две альтернативы:
1. Не включайте a0 в подпоследовательность: тогда максимально возможный вес будет равен максимально возможному весу подпоследовательности {a1, a2,… .an}, которая представлена Y
2. Включите a0: тогда максимально возможный вес будет равен a0 + (каждое число, выбранное в Y, будет делиться на 2) a0 + Y / 2. Здесь вы можете заметить, что Y сам выберет оптимальную подпоследовательность, чтобы максимизировать вес.

Окончательный ответ будет Max (Case1, Case2), то есть Max (Y, a0 + Y / 2). Отсюда Б).
Тест на этот вопрос

Рекомендуемые посты:

ВОРОТА | GATE CS 2010 | Вопрос 65

0.00 (0%) 0 votes