Рубрики

ВОРОТА | GATE CS 2008 | Вопрос 44

Задача подмножества суммы определяется следующим образом. Для заданного набора из n натуральных чисел S = {a1, a2, a3,…, an} и натурального W, есть ли подмножество S, элементы которого суммируются с W? Динамическая программа для решения этой проблемы использует 2-мерный логический массив X с n строками и W + 1 столбцами. X [i, j], 1 <= i <= n, 0 <= j <= W, TRUE, если и только если существует подмножество {a1, a2,…, ai}, элементы которого суммируются с j. Что из следующего справедливо для 2 <= i <= n и ai <= j <= W?
(A) X [i, j] = X [i — 1, j] VX [i, j -ai]
(B) X [i, j] = X [i — 1, j] VX [i — 1, j — ai]
(C) X [i, j] = X [i — 1, j] VX [i, j — ai]
(D) X [i, j] = X [i — 1, j] VX [i -1, j — ai]

Ответ: (Б)
Пояснение: X [I, j] (2 <= i <= n и ai <= j <= W), верно, если верно любое из следующего
1) Сумма весов, исключая ai, равна j, т. Е. Если X [i-1, j] истинно.
2) Сумма весов, включая ai, равна j, т. Е. Если X [i-1, j-ai] истинно, так что мы получаем (j — ai) + ai как j.
Тест на этот вопрос

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

ВОРОТА | GATE CS 2008 | Вопрос 44

0.00 (0%) 0 votes