Образец рюкзака — определите образец и решите с помощью динамического программирования

Введение

Комбинаторная оптимизация – это способ оптимизации, заключающийся в поиске оптимального объекта из конечного набора объектов. У него есть много известных задач, таких как задача коммивояжера, задача о минимальном остовном дереве и задача о рюкзаке.

Задача о рюкзаке – это задача комбинированной оптимизации. Ее также называют проблемой рюкзака. Он получил свое название от следующей задачи максимизации наиболее подходящего выбора предметов первой необходимости, которые могут поместиться в одну сумку для путешествий.

Учитывая набор элементов, каждый из которых имеет вес и значение, определите количество каждого элемента, которое нужно взять в коллекцию, чтобы общий вес был меньше заданного предела, а общее значение было как можно больше.

Пример:

Допустим, есть одна сумка, максимальная вместимость которой составляет 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, чтобы было не болееm0иn1в подмножестве.

Набор 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 будет полностью понят.