Рубрики

Алгоритмы | Динамическое Программирование | Вопрос 7

Задача подмножества суммы определяется следующим образом. Для заданного набора из 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] ∨ X [i, j -ai]
(B) X [i, j] = X [i — 1, j] ∨ X [i — 1, j — ai]
(C) X [i, j] = X [i — 1, j] ∧ X [i, j — ai]
(D) X [i, j] = X [i — 1, j] ∧ X [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

См. Http://espressocode.top/dynamic-programming-subset-sum-problem/ для получения подробной информации.
Тест на этот вопрос

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

Алгоритмы | Динамическое Программирование | Вопрос 7

0.00 (0%) 0 votes