Учитывая вес и прибыль N предметов, мы хотим поместить эти предметы в рюкзак вместимостью C. Цель состоит в том, чтобы получить максимальную прибыль от предметов в рюкзаке. Каждый товар можно выбрать только один раз, так как у нас нет нескольких количеств любого товара.
Пример:
- Предметы: [A, B, C, D]
- Вес: [2, 3, 1, 4]
- Прибыль: [4, 5, 3, 7]
- Вместимость: 5
Давайте попробуем какую-нибудь комбинацию, общий вес которой меньше вместимости 5:
- A + B (общий вес: 5) = 9 прибыль
- C + D (общий вес: 5) = 10 прибыли
- B + C (общий вес: 4) = 8 прибыль
Базовое решение
Нисходящее динамическое программирование с мемоизацией
Мы можем использовать мемоизацию, чтобы преодолеть перекрывающиеся подзадачи. Повторюсь, мемоизация - это когда мы сохраняем результаты всех ранее решенных подзадач и возвращаем результаты из памяти, если мы сталкиваемся с проблемой, которая уже решена.
Поскольку у нас есть два изменяющихся значения (capacity и currentIndex) в нашей рекурсивной функции knapsackRecursive(), мы можем использовать двумерный массив для хранения результатов всех решенных подзадач. Как упоминалось выше, нам необходимо сохранять результаты для каждого подмассива (т.е. для каждого возможного индекса «i») и для каждой возможной емкости «c».
Восходящее динамическое программирование
Давайте попробуем заполнить наш dp[][] массив из вышеприведенного решения, работая по восходящей схеме. По сути, мы хотим найти максимальную прибыль для каждого подмассива и для каждой возможной емкости.
Это означает, что dp[i][c] будет представлять максимальную прибыль от рюкзака для вместимости «c», рассчитанную по первым элементам «i».
Разделение суммы равных подмножеств - код Leetcode # 416
Эта проблема соответствует типу 0/1 ранца. Основное решение методом грубой силы может заключаться в том, чтобы попробовать все комбинации разделения заданных чисел на два набора, чтобы увидеть, есть ли у какой-либо пары наборов одинаковая сумма.
Предположим, что если S представляет общую сумму всех заданных чисел, тогда два равных подмножества должны иметь сумму, равную S/2. Это по существу трансформирует нашу проблему к следующему: «Найти подмножество заданных чисел, общая сумма которых равна S/2».
Восходящее динамическое программирование
Давайте попробуем заполнить наш dp[][] массив из вышеприведенного решения, работая по восходящей схеме. По сути, мы хотим выяснить, можем ли мы сделать все возможные суммы с каждым подмножеством. Это означает, что dp[i][s] будет "истинным", если мы сможем вычислить сумму "s" из первых чисел "i".
Итак, для каждого числа с индексом ‘i’ (0 ‹= i‹ num.length) и суммы ‘s’ (0 ‹= s‹ = S / 2) у нас есть два варианта:
- Исключить номер. В этом случае мы посмотрим, сможем ли мы получить "s" из подмножества, исключая это число:
dp[i-1][s] - Включите число, если его значение не больше "s". В этом случае мы посмотрим, сможем ли мы найти подмножество, чтобы получить оставшуюся сумму:
dp[i-1][s-num[i]]
Если один из двух вышеупомянутых сценариев верен, мы можем найти подмножество чисел с суммой, равной 's'.
Сумма подмножества
Пример:
- Вход [1, 2, 3, 7]
- S = 6
- Выход - - Истина
Эта проблема соответствует шаблону 0/1 ранца и очень похожа на разделение суммы равных подмножеств. Основное решение методом перебора может заключаться в том, чтобы попробовать все подмножества заданных чисел, чтобы увидеть, есть ли в каком-либо наборе сумма, равная «S».
Восходящее динамическое программирование
Мы постараемся выяснить, сможем ли мы сделать все возможные суммы для каждого подмножества, чтобы заполнить массив dp[TotalNumbers][S+1].
Для каждой возможной суммы «s» (где 0 ‹= s‹ = S) у нас есть два варианта:
- Исключить номер. В этом случае мы посмотрим, сможем ли мы получить сумму «s» из подмножества, исключая это число = ›
dp[index-1][s] - Включите число, если его значение не больше "s". В этом случае мы посмотрим, сможем ли мы найти подмножество, чтобы получить оставшуюся сумму = ›
dp[index-1][s-num[index]]
Минимальная разница суммы подмножества
Учитывая набор положительных чисел, разделите набор на два подмножества с минимальной разницей между суммами их подмножеств.
Базовое решение
Предположим, что S1 и S2 - два желаемых подмножества. Основное решение методом перебора может заключаться в том, чтобы попытаться добавить каждый элемент либо в S1, либо в S2, чтобы найти комбинацию, которая дает минимальную разницу сумм между двумя наборами.
Нисходящее динамическое программирование с запоминанием
Мы будем использовать двумерный массив для хранения результатов решенных подзадач. Мы можем однозначно идентифицировать подзадачу с помощью «currentIndex» и «Sum1»; поскольку «Sum2» всегда будет суммой оставшихся чисел.
Вверх дном
Предположим, что S представляет собой общую сумму всех чисел. Итак, то, что мы пытаемся достичь в этой проблеме, - это найти подмножество, сумма которого как можно ближе к S / 2, потому что, если мы можем разделить данный набор на два подмножества с равной суммой, мы получим минимальную разницу т.е. ноль. Это превращает нашу задачу в Сумму подмножества, где мы пытаемся найти подмножество, сумма которого равна заданному числу - в нашем случае S / 2. Если мы не можем найти такое подмножество, мы возьмем подмножество, сумма которого наиболее близка к S / 2. Это легко возможно, так как мы будем вычислять все возможные суммы для каждого подмножества.
По сути, нам нужно вычислить все возможные суммы до «S / 2» для всех чисел. Так как же нам заполнить массив db[TotalNumbers][S/2+1] снизу вверх?
Для каждой возможной суммы «s» (где 0 ‹= s‹ = S / 2) у нас есть два варианта:
- Исключить номер. В этом случае мы посмотрим, сможем ли мы получить сумму «s» из подмножества, исключая это число = ›
dp[index-1][s] - Включите число, если его значение не больше "s". В этом случае мы посмотрим, сможем ли мы найти подмножество, чтобы получить оставшуюся сумму = ›
dp[index-1][s-num[index]]
Если один из двух вышеупомянутых сценариев верен, мы можем найти подмножество с суммой, равной 's'. Мы должны вникнуть в это, прежде чем узнаем, как найти ближайшее подмножество.
Подсчет суммы подмножества
Для набора положительных чисел найдите общее количество подмножеств, сумма которых равна заданному числу «S».
Сверху вниз
Вверх дном
Мы попытаемся выяснить, сможем ли мы сделать все возможные суммы с каждым подмножеством для заполнения массива db[TotalNumbers][S+1].
Итак, на каждом этапе у нас есть два варианта:
- Исключить номер. Подсчитайте все подмножества без заданного числа до заданной суммы = ›
dp[index-1][sum] - Включите число, если его значение не больше, чем «сумма». В этом случае мы посчитаем все подмножества, чтобы получить оставшуюся сумму = ›
dp[index-1][sum-num[index]]
Чтобы найти общие наборы, мы сложим оба из двух вышеупомянутых значений:
dp[index][sum] = dp[index-1][sum] + dp[index-1][sum-num[index]])Целевая сумма
Leetcode # 494
Дан набор положительных чисел (отличных от нуля) и целевая сумма «S». Каждому номеру должен быть присвоен знак «+» или «-». Нам нужно найти общие способы присвоения символов, чтобы сумма чисел была равна целевой «S».
Нас просят найти два подмножества заданных чисел, разность которых равна заданной цели «S». Скажем, «Sum (s1)» обозначает общую сумму набора «s1», а «Sum (s2)» обозначает общую сумму набора «s2». Итак, необходимое уравнение:
Sum(s1) - Sum(s2) = SЭто уравнение можно свести к проблеме суммы подмножеств. Предположим, что «Sum (num)» обозначает общую сумму всех чисел, поэтому:
Sum(s1) + Sum(s2) = Sum(num)Добавим два приведенных выше уравнения:
=> Sum(s1) - Sum(s2) + Sum(s1) + Sum(s2) = S + Sum(num)
=> 2 * Sum(s1) = S + Sum(num)
=> Sum(s1) = (S + Sum(num)) / 2Это по существу превращает нашу задачу в: «Найти количество подмножеств заданных чисел, сумма которых равна»,
=> (S + Sum(num)) / 2