Рубрики

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

Задача подмножества суммы определяется следующим образом. Для заданного набора из 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?

Какая запись массива X, если TRUE, подразумевает, что существует подмножество, элементы которого суммируются с W?
(A) X [1, W]
(B) X [n, 0]
(C) X [n, W]
(D) X [n-1, n]

Ответ: (с)
Объяснение: см. Вопрос 2 http://espressocode.top/data-structures-and-algorithms-set-21/
Тест на этот вопрос

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

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

0.00 (0%) 0 votes