算法系列：动态规划详解（二）背包问题

时间：2024-10-06 21:18:24

前言

继续总结动态规划
本篇打尽背包问题

1、0-1 背包问题

一个典型问题描述：

给你⼀个可装载重量为 W 的背包和 N 个物品，每个物品有重量和价值两个属性。
其中第 i 个物品的重量为 wt[i] ，价值为 val[i] ，
现在让你⽤这个背包装物品，最多能装的价值是多少
  • 1
  • 2
  • 3

根据动态规划进行分析：

  • 状态：背包的容量，每件物品装或不装
  • dp：有两个状态，需要二维数组，对于前 i 个物品，当前背包的容量为 w ，这种情况下可以装的最⼤价值是 dp[i][w]
  • 状态转移：如果没有把第 i 个物品装⼊背包， dp[i][w] = dp[i-1][w] ；如果把第 i 个物品装⼊了背包，那么 dp[i][w] = dp[i-1][w - wt[i-1]] + val[i-1]

如是可以写出解了

我们来看下leet上的几个例子

416. 分割等和子集

给定一个只包含正整数的非空数组。是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。

将其转化为背包问题：
给⼀个可装载重量为 sum / 2 的背包和 N 个物品，每个物品的重量为nums[i] 。现在让你装物品，是否存在⼀种装法，能够恰好将背包装满？

根据上面的分析
写出解

class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        avg, mod = divmod(sum(nums), 2)
        # 不能被2整除
        if mod != 0: return False
        n = len(nums)
        dp = [[1] + [0] * avg for _ in range(n + 1)]
        for i in range(1, n + 1):
            for j in range(1, avg + 1):
                if j - nums[i - 1] >= 0:
                    dp[i][j] = dp[i - 1][j - nums[i - 1]] | dp[i - 1][j]
        return dp[-1][-1]
       
# 优化
class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        avg, mod = divmod(sum(nums), 2)
        # 不能被2整除
        if mod != 0: return False
        n = len(nums)
        dp = [1] + [0] * avg 
        for i in range(1, n + 1):
            for j in range(avg, -1, -1): #从后往前反向遍历
                if j - nums[i - 1] >= 0:
                    dp[j] |= dp[j - nums[i - 1]] 
        return dp[-1]
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
474. 一和零

在计算机界中，我们总是追求用有限的资源获取最大的收益。

现在，假设你分别支配着 m 个 0 和 n 个 1。另外，还有一个仅包含 0 和 1 字符串的数组。

你的任务是使用给定的 m 个 0 和 n 个 1 ，找到能拼出存在于数组中的字符串的最大数量。每个 0 和 1 至多被使用一次。

class Solution:
    def findMaxForm(self, strs: List[str], m: int, n: int) -> int:
        if len(strs) == 0: return 0
        dp=[[[0]*(n+1) for _ in range(m+1)] for _ in range(len(strs)+1)]
        for i in range(1, len(strs)+1):
            ones = strs[i-1].count("1")
            zeros = strs[i - 1].count("0")
            for j in range(m+1):
                for k in range(n+1):
                    dp[i][j][k]=dp[i-1][j][k]
                    if j >= zeros and k >= ones and dp[i][j][k]<dp[i-1][j - zeros][k - ones] + 1:
                        dp[i][j][k] = dp[i - 1][j - zeros][k - ones] + 1
        return dp[-1][-1][-1]

# 优化
class Solution:
    def findMaxForm(self, strs: List[str], m: int, n: int) -> int:
        if len(strs) == 0: return 0
        dp = [[0]*(n+1) for _ in range(m+1)]   #准备很多个背包
        for strs_item in strs:
            item_count0 = strs_item.count('0')
            item_count1 = strs_item.count('1')
            #遍历可容纳的背包 
            for i in range(m, item_count0 - 1, -1):  #采取倒序
                for j in range(n, item_count1 - 1, -1):
                    dp[i][j] = max(dp[i][j], 1 + dp[i-item_count0][j-item_count1]) 
        return dp[m][n]
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27

2、完全背包问题

典型问题描述如下

有⼀个背包，最⼤容量为 amount ，有⼀系列物品 coins ，每个物品的重量为 coins[i] ，每个物品的数量⽆限。
请问有多少种⽅法，能够把背包恰好装满？
  • 1
  • 2

关键在于每个物品数量无限

根据动态规划进行分析：

  • 状态：背包的容量，每件物品装或不装
  • dp：只使⽤前 i 个物品，当背包容量为 j 时，有 dp[i][j] 种⽅法可以装满背包
  • 状态转移：dp[i][j] = dp[i - 1][j] + dp[i][j-coins[i-1]]

如是可以写出解

同样看leet上的例子

322. 零钱兑换

给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
    	n = len(coins)
    	dp = [[float("inf")] * (amount + 1) for _ in range(n+1)]
    	for i in range(n):
    		dp[i][0] = 1
    	for i in range(1, n):
    		for j in range(1, amount):
    			if j-coins[i-1] >= 0:
    				dp[i][j] = dp[i-1][j] + dp[i][j-coins[i-1]]
    			else:
    				dp[i][j] = dp[i-1][j]
    	return dp[-1][-1]
# 优化
class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        # 自底向上
        # dp[i] 表示金额为i需要最少的硬币
        # dp[i] = min(dp[i], dp[i - coins[j]]) j所有硬币
        dp = [float("inf")] * (amount + 1)
        dp[0] = 0
        for i in range(1, amount + 1):
            dp[i] = min(dp[i - c] if i - c >= 0 else float("inf") for c in coins) + 1
        return dp[-1] if dp[-1] != float("inf") else -1
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
518. 零钱兑换 II

给定不同面额的硬币和一个总金额。写出函数来计算可以凑成总金额的硬币组合数。假设每一种面额的硬币有无限个。

class Solution:
    def change(self, amount: int, coins: List[int]) -> int: 
        dp = [0] * (amount + 1)
        dp[0] = 1
        for coin in coins:
            for j in range(coin, amount + 1):
                dp[j] += dp[j - coin]
        return dp[-1]
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8

结语

对经典的背包问题做了个小结

相关文章