Этот вопрос просматривают 36000+ раз, но я не вижу достаточного ответа, который подробно объясняет алгоритм с помощью логики. Поэтому я решил сделать попытку.
Предположение:
Для простоты сначала я сделал предположение, что входной набор X содержит только положительные целые числа, а k положительный. Тем не менее, мы можем настроить алгоритм для обработки отрицательных целых чисел и в случае, если k является отрицательным.
Логика:
Ключ к этому алгоритму или на самом деле любая проблема DP заключается в том, чтобы разбить проблему и начать просто с базового случая. тогда мы можем опираться на базовый случай, используя некоторые знания что мы знаем:
- мы знаем, что если набор
X пуст, то мы не сможем суммировать любое значение k.
- Если набор
X содержит k, то у него есть поднабор суммы k.
- мы знаем, что если подмножество набора
x1, которое является подмножеством X, суммируется с k1, тогда X будет иметь подмножество, которое будет иметь сумму k1, а именно x1.
- у нас есть набор
X = {x1, x1, x3, ......., xn, xn+1}. Мы знаем, что подмножество имеет значение k1, если x1 = {x1, x1, x3, ......., xn} имеет подмножество суммы k - k1.
Пример для иллюстрации 1,2,3,4:
- это легко. если у вас есть пустой набор {}. вы не можете иметь подмножество таким образом
Вы не можете иметь какую-либо подмножество.
Набор X = {4} имеет подмножество суммы 4, потому что 4 само является частью набора
скажем, у вас есть набор x1 = {1,3,5}, который является подмножеством набора X = {1,3,5,2,8}. если x1 имеет подмножество суммы k1 = 8, то это означает, что X также имеет подмножество суммы 8, потому что x1 является подмножеством X
- скажем, у вас есть набор
X = {1,3,5,2,19}, и мы хотим знать, имеет ли он подмножество суммой до 20. Это делает, и один способ узнать, может ли это быть x1 = {1,3,5,2}, может суммироваться с (20 - 19) = 1. Поскольку x1 имеет подмножество суммы 1, тогда, когда мы добавим 19 к множеству x1
мы можем взять это новое число 1 + 19 = 20, чтобы создать желаемую сумму 20.
Динамически построить матрицу
Здорово! Теперь давайте воспользуемся четырьмя логиками и начнем строить с базового варианта. Мы собираемся построить матрицу m. Мы определяем:
матрица m имеет i+1 строки и k + 1 столбцы.
Каждая ячейка матрицы имеет значение true или false.
m [i] [s] возвращает true или false, чтобы указать ответ на этот вопрос: «Используя первые i элементов в массиве, можем ли мы найти подмножество суммы в s?» m[i][s] возвращает true для да и false для нет
(обратите внимание, что ответ из Википедии или большинство людей строят функцию m (i, s), но я подумал, что матрица - это простой способ понять динамическое программирование. Она хорошо работает, когда в наборе или массиве есть только положительные числа) Однако функция route лучше, потому что вам не нужно иметь дело с индексом вне диапазона, сопоставлять индекс массива и сумму с матрицей .....)
Построим матрицу на примере:
X = {1,3,5,2,8}
k = 9
Мы собираемся строить матрицу построчно. В конечном итоге мы хотим знать, что ячейка m [n] [k] содержит true или false.
Первая строка:
Логика 1. говорит нам, что первая строка матрицы должна быть false.
0 1 2 3 4 5 6 7 8 9
_ _ _ _ _ _ _ _ _ _
0| F F F F F F F F F F
1|
2|
3|
4|
5|
Вторая строка и выше:
Затем для второй строки или выше мы можем использовать логику 2,3,4, чтобы помочь нам заполнить матрицу.
- логика 2 говорит нам, что
m[i][s] = (X[i-1] == s) Remembermebr m [i] относится к i-му элементу в X, который является X [i-1]
- логика 3 говорит нам, что
m[i][s] = (m[i-1][s]) это смотрит на указанную выше ячейку.
- логика 4 говорит нам, что
m[i][s] = (m[i-1][s - X[i-1]]) это взгляд на строку выше и слева от X [i-1] ячеек.
Если любой из них true, тогда m[i][s] равен true, в противном случае false. так что мы можем переписать 2,3,4 в m[i][s] = (m[i-1][s] || a[i-1] == s || m[i-1][s - a[i-1]])
Используйте приведенную выше логику для заполнения матрицы m. В нашем примере это выглядит так.
0 1 2 3 4 5 6 7 8 9
_ _ _ _ _ _ _ _ _ _
0| F F F F F F F F F F
1| F T F F F F F F F F
2| F T F T T F F F F F
3| F T F T T T T F T T
4| F T T T T T T T T T
5| F T T T T T T T T T
Теперь воспользуйтесь матрицей для ответа на ваш вопрос:
посмотрите на m[5][9], это оригинальный вопрос. Используя первые 5 элементов (которые являются всеми элементами), можем ли мы найти подмножество суммы до 9 (k)? и ответ указывается той ячейкой, которая является true
Вот код:
import java.util.*;
public class SubSetSum {
public static boolean subSetSum(int[] a, int k){
if(a == null){
return false;
}
//n items in the list
int n = a.length;
//create matrix m
boolean[][] m = new boolean[n + 1][k + 1]; //n + 1 to include 0, k + 1 to include 0
//set first row of matrix to false. This also prevent array index out of bounds: -1
for(int s = 0; s <= k; s++){
m[0][s] = false;
}
//populate matrix m
for(int i = 1; i <= n; i++){
for(int s = 0; s <= k; s++){
if(s - a[i-1] >= 0){ //when it goes left we don't want it to go out of bounds. (logic 4)
m[i][s] = (m[i-1][s] || a[i-1] == s || m[i-1][s - a[i-1]]);
} else {
m[i][s] = (m[i-1][s] || a[i-1] == s);
}
}
}
//print matrix
print(m);
return m[n][k];
}
private static void print(boolean[][] m){
for(int i = 0; i < m.length; i++){
for(int j = 0; j < m[i].length; j++){
if(m[i][j]){
System.out.print("T");
} else {
System.out.print("F");
}
}
System.out.print("\n");
}
}
public static void main(String[] args){
int[] array = {1,3,5,2,8};
int k = 9;
System.out.println(subSetSum(array,k));
}
}
Для построения матрицы m требуется O ((n + 1) (k + 1)), то есть O (nk). кажется, это должно быть многочленом, но это не так! Это на самом деле псевдополином. Читайте об этом здесь
Опять же, это работает, только если вход содержит только положительные числа. Вы можете легко настроить его для работы с отрицательными числами. Матрица будет по-прежнему иметь n + 1 рядов, но B - A + 1 столбцов. Где B - верхняя граница, а A - нижняя граница (+1, чтобы включить ноль). Матрица все равно будет. Вам придется сместить s с нижней границей.
Довольно сложно объяснить проблему ДП поверх текста от начала до конца. Но я надеюсь, что это поможет тем, кто пытается понять эту проблему.