Это пример проблемы с рюкзаком?

Question

У меня есть то, что кажется простой проблемой, но я изо всех сил пытаюсь ее решить. Обращаясь к Google, кажется, что это может быть вариацией проблемы рюкзака, но у меня возникают проблемы с отображением этих решений этой конкретной проблемы.

Допустим, у меня есть два списка натуральных чисел, A и B. I Я хочу найти значение, которое представляет наибольшую общую сумму между этими двумя списками.

A: [6, 1]
B: [5, 3, 1]

Здесь ответ равен 6, потому что это самая большая сумма, которую обычно можно создать в обоих списках (удалив 1 в списке A и удаление 3 в списке B).

Я могу наивно решить это в O (2 ^ n), но я предполагаю, что есть гораздо более эффективный подход с помощью динамического программирования c, хотя dp не моя сила.

Это проблема с рюкзаком? Любые указатели относительно того, как я должен сопоставить проблему ранца classi c с этой проблемой двух списков?

Answer 1

Эту проблему можно решить в O(nW), где n - это количество всех элементов, а W - это сумма всех элементов в списках.

Обрабатывает каждый список отдельно. Пусть dp1[i][j] будет истинным, если есть подмножество первых i элементов первого списка, сумма которых равна j (0 <= i <= n1, 0 <= j <= W1). dp1 может быть заполнено с использованием повторяющейся формулы:

• dp1[0][0] равно true
• dp1[0][j] равно false (j != 0)
• РЕДАКТИРОВАТЬ : dp1[i][0] равно true (i != 0)
• dp1[i][j] равно true, если:
  • (j >= list.get(i) И dp[i - 1][j - list.get(i)] равно true)
  • ИЛИ dp[i - 1][j] равно true

Затем заполните dp2[i][j] для второго списка. Затем просто найдите максимальное число S, для которого dp1[n1][S] и dp2[n2][S] равны true.