Размещение отдельных предметов в мешках для максимизации прибыли
Задача о рюкзаке — это комбинаторная оптимизационная задача. Чтобы решить эту проблему, мы можем следовать следующему:
Общая стратегия:
- Найти базовый случай
- Найти рекуррентное соотношение
- Повторное использование вычисленных значений
- Напишите восходящее итеративное решение
Имея веса w и прибыль p для N товаров, нужно найти подмножество этих предметы, которые принесут максимальную прибыль, но их совокупная сумма не должна превышать общую вместимость рюкзака C.
Profits = [20, 5, 10, 40, 15, 25] Weights = [1, 2, 3, 8, 7, 4] Capacity = 10
Мы можем решить эту проблему снизу вверх. Сначала мы решаем меньшие подзадачи, а затем решаем более крупные подзадачи, используя уже решенные проблемы. Следующий восходящий подход вычисляет dp[i][j] для каждого 1 <= i <= n и 0 <= j <= W, что является максимальной прибылью, которая может быть достигнута с весом, меньшим или равным j, и с использованием предметов до первых i предметов.
Подход здесь заключается в создании матрицы со столбцами C (общая вместимость) и строками n (количество элементов). В этой матрице каждая ячейка представляет максимальную прибыль путем выбора количества элементов в этой строке и общего веса в этом столбце.
Из приведенной выше таблицы видно, что существуют некоторые естественные базовые случаи. Если мы говорим, что общий вес равен нулю, то мы не можем выбрать ни один элемент, поэтому 1-й столбец матрицы заполнен нулевой прибылью. Точно так же, если мы не выбираем какой-либо элемент, у нас нет прибыли, поэтому в первой строке устанавливается нулевая прибыль. Для других ячеек матрицы мы используем график решений и заполняем прибыль. Код для той же логики закодирован ниже:
def knapsack(p, w, c):
n = len(p)
dp = [[0 for _ in range(c + 1)] for _ in range(n + 1)]
for i in range(1, len(p) + 1):
for j in range(c + 1):
if w[i - 1] > j:
dp[i][j] = dp[i - 1][j]
else:
dp[i][j] = max(dp[i - 1][j], \
dp[i - 1][j - w[i - 1]] + p[i - 1])
Оптимизация пространства по приведенной выше логике:
def knapsack(p, w, c):
n = len(p)
dp = [0 for i in range(c+1)]
for i in range(1, n+1):
for j in range(c, 0, -1):
if w[i-1] <= j:
dp[j] = max(dp[j], dp[j-w[i-1]]+p[i-1])
return dp[c]
Сумма подмножества
Учитывая массив и цель, возвращайте true, если существует подмножество, сумма которого равна данной цели.
nums = [2, 3, 7, 8, 10] target = 11 OP: True
Реализация кода
def isSubsetSum(nums, target):
n = len(nums)
dp = [[False for _ in range(target + 1)] for _ in range(n+1)]
for i in range(n):
dp[i][0] = True
for i in range(1, n+1):
for j in range(1, target+1):
if nums[i-1] <= j:
dp[i][j] = dp[i-1][j-nums[i-1]] or dp[i-1][j]
else:
dp[i][j] = dp[i-1][j]
return dp[n][target]
Количество подмножеств с заданной суммой
Учитывая массив и цель, возвращают количество подмножеств, сумма которых равна данной цели.
nums = [2, 3, 5, 6, 8, 10]
target = 10
OP = 3 {10}, {2, 8}, {2, 3, 5}
Реализация кода
def subsetCount(nums, target):
n = len(nums)
dp = [ [0]*(target+1) for _ in range(n+1)]
for i in range(target+1):
dp[0][i] = 0
for i in range(n+1):
dp[i][0] = 1
for i in range(1, n+1):
for j in range(1, target+1):
if nums[i-1] <= j:
dp[i][j] = dp[i-1][j] + dp[i-1][j-nums[i-1]]
else:
dp[i][j] = dp[i-1][j]
return dp[n][target]
Раздел равной суммы
Для заданного массива проверьте, можно ли его разделить на два массива так, чтобы сумма отдельных массивов была равна.
nums = [ 11, 5, 1, 5]
OP = True {11} {1, 5, 5}
Реализация кода
def isSubsetSum(nums, target):
n = len(nums)
dp = [[False for _ in range(target + 1)] for _ in range(n+1)]
for i in range(n):
dp[i][0] = True
for i in range(1, n+1):
for j in range(1, target+1):
if nums[i-1] <= j:
dp[i][j] = dp[i-1][j-nums[i-1]] or dp[i-1][j]
else:
dp[i][j] = dp[i-1][j]
return dp[n][target]
def canPartition(nums):
tsum = sum(nums)
if tsum%2 != 0:
return False
else:
return isSubsetSum(nums, tsum//2)
Подсчет суммы подмножества с заданной разностью
Пусть суммы двух подмножеств равны s1 и s2.
s1 - s2 = target(given difference) s1 + s2 = sum(nums) 2s1 = target + sum(nums) s1 = (target + sum(nums))/2
Теперь проблема сводится к нахождению количества подмножеств с новой целью (цель+сумма(числа)/2.
Реализация кода
def subsetCount(nums, target):
n = len(nums)
dp = [ [0]*(target+1) for _ in range(n+1)]
for i in range(target+1):
dp[0][i] = 0
for i in range(n+1):
dp[i][0] = 1
for i in range(1, n+1):
for j in range( target+1):
if nums[i-1] <= j:
dp[i][j] = dp[i-1][j] + dp[i-1][j-nums[i-1]]
else:
dp[i][j] = dp[i-1][j]
return dp[n][target]
def subsetWithGivenDiff(nums, target):
tsum = sum(nums)
if (abs(target) > tsum or (tsum + target) % 2 != 0):
return 0
s1 = (tsum + target)//2
ans = subsetCount(nums, s1)
return ans
Целевая сумма
Вам дан массив целых чисел nums и целое число target. Вы хотите построить выражение из чисел, добавив один из символов '+' и '-' перед каждым целым числом в числах, а затем соединив все целые числа. Возвращает количество различных выражений, которые вы можете построить, которые оцениваются как target.
Input: nums = [1,1,1,1,1], target = 3 Output: 5 Explanation: There are 5 ways to assign symbols to make the sum of nums be target 3. -1 + 1 + 1 + 1 + 1 = 3 +1 - 1 + 1 + 1 + 1 = 3 +1 + 1 - 1 + 1 + 1 = 3 +1 + 1 + 1 - 1 + 1 = 3 +1 + 1 + 1 + 1 - 1 = 3
Поскольку у нас есть только два варианта «+» или «-», мы можем рассматривать это как разделение на два подмножества и затем получение их различий. например +1 +1 +1 -1 -1 = 3. Это можно записать как (1+1+1)-(1+1). Мы вычисляем разницу суммы этих двух наборов (1, 1, 1) → с положительными знаками, сумма = 3 и (1, 1) → с отрицательными знаками, сумма = 2. Таким образом, разность 1 становится целью.
Реализация кода
def subsetCount(nums, target):
n = len(nums)
dp = [ [0]*(target+1) for _ in range(n+1)]
for i in range(target+1):
dp[0][i] = 0
for i in range(n+1):
dp[i][0] = 1
for i in range(1, n+1):
for j in range( target+1):
if nums[i-1] <= j:
dp[i][j] = dp[i-1][j] + dp[i-1][j-nums[i-1]]
else:
dp[i][j] = dp[i-1][j]
return dp[n][target]
def findTargetSumWays(nums, target):
tsum = sum(nums)
if (abs(target) > tsum or (tsum + target) % 2 != 0):
return 0
s1 = (tsum + target)//2
ans = subsetCount(nums, s1)
return ans
Удачного кодирования!
Дополнительные материалы на PlainEnglish.io. Подпишитесь на нашу бесплатную еженедельную рассылку новостей. Подпишитесь на нас в Twitter и LinkedIn. Посетите наш Community Discord и присоединитесь к нашему Коллективу талантов.
