Введение
Комбинаторная оптимизация – это способ оптимизации, заключающийся в поиске оптимального объекта из конечного набора объектов. У него есть много известных задач, таких как задача коммивояжера, задача о минимальном остовном дереве и задача о рюкзаке.
Задача о рюкзаке – это задача комбинированной оптимизации. Ее также называют проблемой рюкзака. Он получил свое название от следующей задачи максимизации наиболее подходящего выбора предметов первой необходимости, которые могут поместиться в одну сумку для путешествий.
Учитывая набор элементов, каждый из которых имеет вес и значение, определите количество каждого элемента, которое нужно взять в коллекцию, чтобы общий вес был меньше заданного предела, а общее значение было как можно больше.
Пример:
Допустим, есть одна сумка, максимальная вместимость которой составляет 15 кг для перевозки предметов. Имеются заданные наборы предметов, каждому из которых присвоен вес со значением прибыли. Таким образом, задача о рюкзаке определяет, что каждый предмет должен максимизировать прибыль, которую можно получить от предметов, хранящихся в сумке.
Типы задач о рюкзаке
Есть три типа задач о рюкзаке:
- 0/1 Проблема с рюкзаком
- Задача об ограниченном рюкзаке
- Неограниченная задача о рюкзаке
0/1 Задача о рюкзаке
Это очень распространенная проблема рюкзаков. Он ограничивает количество элементов каждого вида нулем или единицей.
Пример:
Допустим, Амир хочет взять с собой в поездку n вещей, и у него есть следующее условие:
- Вес предметаi равен wi, и все предметы разные.
- Предметы должны перевозиться в рюкзаке, грузоподъемность которого равна c: (a) При суммировании весов предметов ≤ c все n предметов можно переносить в рюкзаке. (b) Когда сумма весов элементов › c, некоторые элементы должны быть оставлены.
Если нам нельзя брать дробные суммы, то это проблема рюкзака 0/1.
Задача об ограниченном рюкзаке
Задача ограниченного рюкзака ограничивает количество каждого предмета определенным значением. Он снимает ограничение, заключающееся в том, что существует только один элемент каждого типа, но ограничивает количество xiкопий каждого типа элементов максимальным неотрицательным целым числом с.
Неограниченная задача о рюкзаке
Задача о неограниченном рюкзаке не накладывает ограничений на количество каждого предмета. Элементы могут повторяться.
0/1 Вопросы о рюкзаке — ограничено
Максимизируйте прибыль вора
Вор входит в магазин с сумкой и начинает воровать товары из магазина. Максимальная вместимость его сумки 10 кг. Он не может положить в сумку больше 10 кг. Он хочет положить в свою сумку только те предметы, от которых он может получить больше прибыли.(Здесь вор не может делить или разбирать предметы, он может взять предмет или нет ( 0–1 свойство).
price = [ 20, 5, 10, 40, 15, 25 ] weight = [ 1, 2, 3, 8, 7, 4 ] bagWeight = 10 kg Output: 60 price = 20 + 40 = 60 total weight = 1 + 8 = 9 < bagWeight
Решение
Эта проблема может быть решена с использованием двух различных возможностей:
- Включите текущий предмет в ранец и повторите для оставшихся предметов, а затем уменьшите вес.
- Не включайте текущий предмет в ранец и повторяйте для оставшихся предметов.
Используя рекурсию:
def getMaxProfitForThief(price, weight, n, bagCapacity): if bagCapacity < 0: return float('-inf') if n < 0 or bagCapacity == 0: return 0 exclude = getMaxProfitForThief(price, weight, n-1, bagCapacity) include = getMaxProfitForThief(price, weight, n-1, bagCapacity - weight[n]) + value[n] return max(exclude, include) if __name__ == '__main__': price = [ 20, 5, 10, 40, 15, 25 ] weight = [ 1, 2, 3, 8, 7, 4 ] bagCapacity = 10 getMaxProfitForThief(price, weight, len(price) - 1, bagCapacity)
Используя динамическое программирование (запоминание):
def getMaxProfitForThief(price, weight, n, bagCapacity, memo): if bagCapacity < 0: return float('-inf') if n < 0 or bagCapacity == 0: return 0 key = str(n) + '-' + str(bagCapacity) if key in memo: return memo[key] exclude = getMaxProfitForThief(price, weight, n-1, bagCapacity, memo) include = getMaxProfitForThief(price, weight, n-1, bagCapacity - weight[n], memo) + value[n] memo[key] = max(exclude, include) return memo[key] if __name__ == '__main__': price = [ 20, 5, 10, 40, 15, 25 ] weight = [ 1, 2, 3, 8, 7, 4 ] bagCapacity = 10 getMaxProfitForThief(price, weight, len(value) - 1, bagCapacity, {})
Используя динамическое программирование (табулирование):
def getMaxProfitForThief(price, weight, bagCapacity): n = len(price) dp = [[0 for _ in range(W + 1)] for _ in range(n + 1)] for i in range(1, n + 1): for j in range(1, bagCapacity + 1): if weight[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]] + v[i-1]) return dp[n][bagCapacity] if __name__ == '__main__': price = [ 20, 5, 10, 40, 15, 25 ] weight = [ 1, 2, 3, 8, 7, 4 ] bagCapacity = 10 getMaxProfitForThief(price, weight, bagCapacity)
Проблема суммы подмножества
Существует набор неотрицательных целых чисел, и сумма целевых значений определяет, существует ли подмножество данного набора с суммой, равной заданной целевой сумме.
arr = [3, 34, 4, 12, 5, 2] target = 9 Output: True Explanation: There is a subset (4, 5) with target sum 9.
Решение
Используя рекурсию:
def getSubset(arr, n, target): if target == 0: return True if n == 0: return False if arr[n-1] > target: return getSubset(arr, n-1, target) return getSubset(arr, n-1, target - arr[n-1]) or getSubset(arr, n-1, target) if __name__ == '__main__': arr = [3, 34, 4, 12, 5, 2] target = 9 getSubset(arr, len(arr)-1, target)
Используя динамическое программирование (табулирование):
def getSubset(arr, target): n = len(arr) dp = [[False for _ in range(target + 1)] for _ in range(n+1)] for i in range(n+1): dp[i][0] = True for i in range(1, n+1): for j in range(1, target+1): if arr[i-1] > j: dp[i][j] = dp[i-1][j] else: dp[i][j] = dp[i-1][j] or dp[i-1][j-arr[i-1]] return dp[n][target] if __name__ == '__main__': arr = [3, 34, 4, 12, 5, 2] target = 9 getSubset(arr, target)
Раздел равной суммы подмножества
Учитывая непустые положительные целые числа, найдите, можно ли разбить массив на два подмножества так, чтобы сумма элементов в обоих подмножествах была равна.
Input: nums = [1,5,11,5] Output: true Explanation: The array can be partitioned as [1, 5, 5] and [11].
Решение:
def canPartition(nums): n = len(nums) total = sum(nums) if total % 2 != 0: return False W = total // 2 dp = [[False for _ in range(W + 1)] for _ in range(n + 1)] for i in range(n + 1): dp[i][0] = True for i in range(1, n + 1): for j in range(1, W + 1): if nums[i-1] > j: dp[i][j] = dp[i-1][j] else: dp[i][j] = dp[i-1][j] or dp[i-1][j-nums[i-1]] return dp[n][W] if __name__ == '__main__': nums = [1,5,11,5] canPartition(nums)
Количество подмножеств с суммой, равной цели
Учитывая непустой массив с элементами и одной целью, найдите количество подмножеств с суммой, равной цели.
Input: arr = [1, 2, 3, 3] target = 6 Output: 3 Explanation: All possible subsets are = [1, 2, 3], [1, 2, 3], [3, 3]
Решение:
def getCountOfSubset(nums, target): n = len(nums) dp = [[0 for _ in range(target + 1)] for _ in range(n + 1)] dp[0][0] = 1 for i in range(1, n + 1): for j in range(target + 1): if nums[i-1] > target: dp[i][j] = dp[i-1][j] else: dp[i][j] = dp[i-1][j] + dp[i-1][j-nums[i-1]] return dp[n][target] if __name__ == '__main__': nums = [ 3, 3, 3, 3 ] target = 6 getCountOfSubset(nums, target)
Другой подход:
def getCountSubsets(arr, target): n = len(arr) dp = [[0 for _ in range(target + 1)] for _ in range(n + 1)] dp[0][0] = 0 for i in range(1, n + 1): for j in range(target + 1): if arr[i-1] > j: dp[i][j] = dp[i-1][j] else: dp[i][j] = max(dp[i-1][j], dp[i-1][j-arr[i-1]] + 1) return dp[n][target] arr = [1, 2, 3, 3] target = 6 getCountSubsets(arr, target)
Целевая сумма
задан массив целых чисел nums
и целое число target
.
Вы хотите построить выражение из чисел, добавив один из символов '+'
и '-'
перед каждым целым числом в числах, а затем соединив все целые числа.
- Например, если
nums = [2, 1]
, вы можете добавить'+'
перед2
и'-'
перед1
и соединить их, чтобы построить выражение"+2-1"
.
Возвращает количество различных выражений, которые вы можете построить, что равно 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
Решение:
def findTargetSumWays(nums, target): n = len(nums) total = sum(nums) if target > total: return 0 if (target + total) % 2 != 0: return 0 s1 = (total + target) // 2 dp = [[0] * (s1 + 1) for i in range(n + 1)] if len(dp) <= 0 or len(dp[0]) == 0: return 0 dp[0][0] = 1 for i in range(1, n + 1): for j in range(s1+1): if nums[i-1] > j: dp[i][j] = dp[i-1][j] else: dp[i][j] = dp[i-1][j] + dp[i-1][j - nums[i-1]] return dp[n][s1] if __name__ == '__main__': nums = [1,1,1,1,1] target = 3 findTargetSumWays(nums, target)
Последний каменный груз II
Вам дан массив целых чисел stones
, где stones[i]
— вес камня ith
.
Мы играем в игру с камнями. На каждом ходу мы выбираем любые два камня и сталкиваем их вместе. Предположим, что камни имеют вес x
и y
с x <= y
. Результат этого удара:
- Если
x == y
, оба камня уничтожаются, и - Если
x != y
, камень весомx
уничтожается, а камень весомy
имеет новый весy - x
.
В конце игры остается не более одного камня.
Возвращает наименьший возможный вес левого камня. Если камней не осталось, верните 0
.
Input: stones = [2,7,4,1,8,1] Output: 1 Explanation: We can combine 2 and 4 to get 2, so the array converts to [2,7,1,8,1] then, we can combine 7 and 8 to get 1, so the array converts to [2,1,1,1] then, we can combine 2 and 1 to get 1, so the array converts to [1,1,1] then, we can combine 1 and 1 to get 0, so the array converts to [1], then that's the optimal value.
Решение:
def lastStoneWeightII(stones): n = len(stones) total = sum(stones) target = total // 2 dp = [0 for i in range(target + 1)] for stone in stones: for w in range(target, stone-1, -1): dp[w] = max(dp[w], dp[w-stone] + stone) return (total - (2 * dp[target])) if __name__ == '__main__': stones = [2,7,4,1,8,1] lastStoneWeightII(stones)
Идеальные квадраты
Получив целое число n
, верните наименьшее количество чисел с полным квадратом, которые в сумме дают n
.
Идеальный квадрат – это целое число, являющееся квадратом целого числа; другими словами, это произведение некоторого целого числа на самого себя. Например, 1
, 4
, 9
и 16
являются правильными квадратами, а 3
и 11
— нет.
Input: n = 12 Output: 3 Explanation: 12 = 4 + 4 + 4.
Решение:
import math def numSquares(n): square_nums = [i ** 2 for i in range(1, int(math.sqrt(n)) + 1)] dp = [float('inf')] * (n + 1) dp[0] = 0 for i in range(1, n + 1): for square_num in square_nums: if i < square_num: break dp[i] = min(dp[i], dp[i - square_num] + 1) return dp[-1] if __name__ == '__main__': n = 12 numSquares(n)
Единицы и нули
Вам дан массив двоичных строк strs
и два целых числа m
и n
.
Возвратите размер наибольшего подмножества strs
, чтобы было не болееm
0
иn
1
в подмножестве.
Набор x
является подмножеством набора y
, если все элементы x
также являются элементами y
.
Input: strs = ["10","0001","111001","1","0"], m = 5, n = 3 Output: 4 Explanation: The largest subset with at most 5 0's and 3 1's is {"10", "0001", "1", "0"}, so the answer is 4. Other valid but smaller subsets include {"0001", "1"} and {"10", "1", "0"}. {"111001"} is an invalid subset because it contains 4 1's, greater than the maximum of 3.
Решение:
Рекурсивный подход:
def findMaxForms(strs, m, n, index): if m < 0 or n < 0: return -1 if index >= len(strs): return 0 include = findMaxForms(strs, m-strs[index].count('0'), n - strs[index].count('1'), index + 1) + 1 exclude = findMaxForms(strs, m, n, index + 1) return max(include, exclude)
Динамический подход:
def findMaxForm(strs, m, n): dp = [[0] * (n + 1) for _ in range(m + 1)] for s in strs: zeros = s.count("0") ones = s.count("1") for i in range(m, zeros-1, -1): for j in range(n, ones-1, -1): dp[i][j] = max( 1 + dp[i - zeros][j- ones], dp[i][j] ) return dp[m][n] if __name__ == '__main__': strs = ["10","0001","111001","1","0"] m = 5 n = 3 findMaxForm(strs, m, n)
Целочисленный разрыв
Получив целое число n
, разбейте его на сумму k
целых положительных чисел, где k >= 2
, и максимизируйте произведение этих целых чисел.
Возвратите максимальный продукт, который вы можете получить.
Input: n = 2 Output: 1 Explanation: 2 = 1 + 1, 1 × 1 = 1.
Решение:
Рекурсивный подход:
def integerBreak(n, total): if n <= 1: return 1 exclude = integerBreak(n-1, total) include = 0 if total >= n: include = integerBreak(n, total-n) * n return max(include, exclude) integerBreak(n-1, n)
Динамический подход:
def integerBreak(n): dp = [0]*(n+1) dp[2] = 1 for i in range(3, n+1): for j in range(1, i-1): dp[i] = max(dp[i], j*max(i-j, dp[i-j])) return dp[-1] if __name__ == '__main__': n = 2 integerBreak(n)
Разница между 0/1 ограниченным и неограниченным рюкзаком
Уже подобранные элементы из массива не учитываются во второй раз и не повторяются в 0/1 Bounded Knapsack.
Однако в Unbounded Knapsack весь массив рассматривается заново.
Пример:
Рюкзак 0/1
def getMaxProfit(value, weight, bagWeight, n): if bagWeight < 0: return float('-inf') if n < 0 or bagWeight == 0: return 0 include = getMaxProfit(value, weight, bagWeight - weight[n-1], n-1) + value[n-1] exclude = getMaxProfit(value, weight, bagWeight, n-1) return max(include, exclude) if __name__ == '__main__': value = [25, 30, 15] weight = [15, 5, 10 ] bagWeight = 100 result = getMaxProfit(value, weight, bagWeight, len(value)-1) print(result)
Неограниченный рюкзак
def getMaxProfit(value, weight, bagWeight, n): if bagWeight < 0: return float('-inf') if n < 0 or bagWeight == 0: return 0 include = getMaxProfit(value, weight, bagWeight - weight[n-1], n) + value[n-1] exclude = getMaxProfit(value, weight, bagWeight, n-1) return max(include, exclude) if __name__ == '__main__': value = [25, 30, 15] weight = [15, 5, 10 ] bagWeight = 100 result = getMaxProfit(value, weight, bagWeight, len(value)-1) print(result)
Здесь, в приведенной выше рекурсивной функции, вы можете найти одно отличие: значение общей длины (’n’) массива (значений или веса) не уменьшается при включении прибыли. Она уменьшается только тогда, когда не учитывается прибыль. Но в Bounded Knapsack значение «n» каждый раз уменьшается.
include = getMaxProfit(value, weight, bagWeight - weight[n-1], n) + value[n-1]
0/1 Вопросы о рюкзаке — без ограничений
Размен монет
Вам дан целочисленный массив coins
, представляющий монеты разного номинала, и целое число amount
, представляющее общую сумму денег.
Верните наименьшее количество монет, необходимое для получения этой суммы. Если эта сумма денег не может быть компенсирована какой-либо комбинацией монет, верните -1
.
Вы можете предположить, что у вас есть бесконечное количество монет каждого вида.
Input: coins = [1,2,5], amount = 11 Output: 3 Explanation: 11 = 5 + 5 + 1
Решение:
Рекурсивный подход:
def coinChange(coins, amount, n): if amount == 0: return 0 if amount < 0 or n < 0: return float("inf") if coins[n] > amount: return coinChange(coins, amount, n-1) exclude = coinChange(coins, amount, n -1) include = coinChange(coins, amount - coins[n], n) + 1 return min(include, exclude) if __name__ == '__main__': coins = [1, 2, 5] amount = 11 result = coinChange(coins, amount, len(coins)-1) print(result)
Динамический подход:
def coinChange(coins, amount): dp = [float("inf")] * (amount + 1) dp[0] = 0 for a in range(1, amount + 1): for coin in coins: if a - coin >= 0: dp[a] = min(dp[a], 1 + dp[a - coin]) if dp[amount] != float("inf"): return dp[amount] return -1 if __name__ == '__main__': coins = [1,2,5] amount = 11 coinChange(coins, amount)
Размен монет 2
Вам дан целочисленный массив coins
, представляющий монеты разного номинала, и целое число amount
, представляющее общую сумму денег.
Возвращает количество комбинаций, составляющих эту сумму. Если эту сумму денег нельзя компенсировать ни одной комбинацией монет, вернуть 0
.
Вы можете предположить, что у вас есть бесконечное количество монет каждого вида.
Ответ гарантировано соответствует 32-разрядному целому числу со знаком.
Input: amount = 5, coins = [1,2,5] Output: 4 Explanation: there are four ways to make up the amount: 5=5 5=2+2+1 5=2+1+1+1 5=1+1+1+1+1
Решение:
Рекурсивный подход:
def change(coins, amount, n): if amount == 0: return 1 if n == 0: return 0 if coins[n-1] > amount: return change(coins, amount, n -1) include = change(coins, amount - coins[n-1], n) exclude = change(coins, amount, n -1) return (include + exclude) if __name__ == '__main__': amount = 5 coins = [1,2,5] result = change(coins, amount, len(coins)) print(result)
Динамический подход:
class Solution(object): def change(self, amount, coins): """ :type amount: int :type coins: List[int] :rtype: int """ dp = [0] * (amount + 1) dp[0] = 1 for coin in coins: for i in range(coin, amount + 1): dp[i] += dp[i-coin] return dp[-1] if __name__ == '__main__': amount = 5 coins = [1,2,5] change(amount, coins)
Сумма комбинаций IV
Учитывая массив различных целых чисел nums
и целевое целое число target
, верните количество возможных комбинаций, которые в сумме составляют target
.
Тестовые примеры генерируются таким образом, чтобы ответ умещался в виде 32-разрядного целого числа.
Input: nums = [1,2,3], target = 4 Output: 7 Explanation: The possible combination ways are: (1, 1, 1, 1) (1, 1, 2) (1, 2, 1) (1, 3) (2, 1, 1) (2, 2) (3, 1) Note that different sequences are counted as different combinations.
Решение
class Solution(object): def combinationSum4(self, nums, target): """ :type nums: List[int] :type target: int :rtype: int """ dp = [ 0 for _ in range(target+1) ] dp[0] = 1 for i in range(target): for num in nums: if i + num < target + 1: dp[i+num] += dp[i] return dp[-1] if __name__ == '__main__': nums = [1,2,3] target = 4 combinationSum4(nums, target):
Минимальная стоимость билетов
Вы запланировали поездку на поезде на год вперед. Дни года, в которые вы будете путешествовать, задаются в виде целочисленного массива days
. Каждый день представляет собой целое число от 1
до 365
.
Билеты на поезд продаются тремя способами:
- пропуск на 1 день продается за
costs[0]
долларов, - пропуск на 7 дней продается за
costs[1]
долларов, а - пропуск на 30 дней продается за
costs[2]
долларов.
Проездные позволяют столько дней подряд путешествовать.
- Например, если мы получили пропуск на 7-дневный день
2
, мы можем путешествовать в течение7
дней:2
,3
,4
,5
,6
,7
и8
.
Возвращает минимальное количество долларов, которое вам нужно тратить каждый день в заданном списке дней.
Input: days = [1,4,6,7,8,20], costs = [2,7,15] Output: 11 Explanation: For example, here is one way to buy passes that lets you travel your travel plan: On day 1, you bought a 1-day pass for costs[0] = $2, which covered day 1. On day 3, you bought a 7-day pass for costs[1] = $7, which covered days 3, 4, ..., 9. On day 20, you bought a 1-day pass for costs[0] = $2, which covered day 20. In total, you spent $11 and covered all the days of your travel.
Решение:
class Solution(object): def mincostTickets(self, days, costs): """ :type days: List[int] :type costs: List[int] :rtype: int """ dp = [0 for _ in range(days[-1] + 1)] for i in range(1, days[-1] + 1): if i in days: if i < 7: dp[i] = min(dp[i - 1] + costs[0], dp[0] + costs[1], dp[0] + costs[2]) elif i < 30: dp[i] = min(dp[i - 1] + costs[0], dp[i - 7] + costs[1], dp[0] + costs[2]) else: dp[i] = min(dp[i - 1] + costs[0], dp[i - 7] + costs[1], dp[i - 30] + costs[2]) else: dp[i] = dp[i-1] return dp[-1] if __name__ == '__main': days = [1,4,6,7,8,20] costs = [2,7,15] mincostTickets(days, costs)
Анализ сложности задачи о рюкзаке
В общем случае известно, что задача о рюкзаке является NP-трудной. Это означает, что для этой задачи не известен полиномиальный алгоритм. Здесь мы используем жадный эвристический подход, который не может гарантировать оптимальное решение.
Заключение
Задача о рюкзаке — задача комбинаторной оптимизации. Существует множество формулировок задач, основанных на шаблонах задачи о рюкзаке. Их можно легко решить с помощью подхода динамического программирования, когда Knapsack будет полностью понят.