Отже, у мене є заданий набір C з n натуральних чисел(c_1, ..., c_n). Завдання полягає в тому, щоб знайти два підмножини A і B з C, де A містить тільки позитивні числа, а B містить лише негативи числа в C. Сума двох підмножин А і B повинна потім підсумовувати до числа d (d завжди позитивний) Мені потрібно з'ясувати, чи існують два таких підмножини, і якщо так, то які числа вони містять.
For example: {3, 5, 6, 13, 24} // d = 12
=> solution: true: {5, 13} {-6}
Я знаю, що це варіація суми підмножиниПроблема, і я бачив деякі рішення для аналогічної проблеми (підмножина сума з негативними числами), але мені потрібно вирішити проблему, використовуючи динамічне програмування. Більшість рішень, я бачив роботу з рекурсією, а не з DP.
Я думаю, мені потрібен 3D-булевський таблиця S (i, j, k) зрозмір (n * n * d). Але коли S (i, j, k) істинно і коли помилково? Тому що я завжди маю перевірити всі можливі способи обчислення суми, використовуючи k-номер, де вони можуть бути як позитивними, так і негативними (наприклад: для 4 чисел {1,2,3,4} є 2 ^ 4 способи упорядкування їх: 1 + 2 + 3 + 4, 1 - 2 + 3 + 4, 1 - 2 - 3 + 4, ..., -1 +2 - 3 - 4, 1 - 2 - 3 - 4)
Моє мислення правильне чи я вже роблю щось не так?
Відповіді:
1 для відповіді № 1Одним з підходів є використання стандартного алгоритму сукупності динамічного програмування підмножини на множині, що складається з (c_1, c_2, ..., c_n, -c_1, -c_2, ..., - c_n).
Це знайде підмножина, яка дорівнює d (або довести, що цього не існує).
Встановіть A на всі позитивні числа у підмножині, а B - на всі негативні числа.
Можливо, ви також хочете видалити будь-які номери, що з'являються як в A, так і в B (наприклад, якщо у вас є 3 в A і 3 у B, ви можете видалити обидва, не змінюючи суму).