背包九讲

01背包

特点：

• 每种物品只有一件，选择放/不放

状态转移方程

大循环是每个物品，小循环是价值

for i in range(1, n):
  for j in range(ci, v+1):
    dp[i][j] = max(dp[i-1][j], dp[i-1][j-ci])

优化

j从v到0，可以少一维数组

for i in range(1, n):
  for j in range(v, 0, -1):
    dp[j] = max(dp[j], dp[j-ci]+wi)

初始化

初始化要是，没有任何物品可以放的时候，依然合法。

• 要装满

初始值=负无穷大。

没东西放，就未定义

• 不一定装满

初始值=0

没东西放，价值为0

leetcode例子

416 分割等和子集

• n件物品：len(nums)

• 容量v：sum(nums)//2

• 放入损耗ci：0

• 获得价值wi：nums[i]

• 装满：初始化为false

class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        n = len(nums)
        target = sum(nums)
        if target % 2 != 0:
            return False
        target //= 2
        dp = [[False]*(target+1) for _ in range(n)]
        dp[0][0] = True
        for i in range(1, n):
            for j in range(0, target+1):
                dp[i][j] = max(dp[i-1][j], dp[i-1][j-nums[i]])
        return dp[-1][-1]

Runtime: 3032 ms, faster than 5.11% of Python3 online submissions for Partition Equal Subset Sum.

Memory Usage: 16.4 MB, less than 9.09% of Python3 online submissions for Partition Equal Subset Sum.

class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        n = len(nums)
        target = sum(nums)
        if target % 2 != 0:
            return False
        target //= 2
        dp = [False]*(target+1)
        dp[0] = True
        for i in range(1, n):
            for j in range(target, nums[i]-1, -1):
                dp[j] = dp[j] or dp[j-nums[i]]
        return dp[-1]

Runtime: 780 ms, faster than 48.92% of Python3 online submissions for Partition Equal Subset Sum. Memory Usage: 12.7 MB, less than 100.00% of Python3 online submissions for Partition Equal Subset Sum.

322 零钱兑换

每个硬币最多选择一次：

• n件物品：len(coins)

• 容量v：amount

• 放入损耗ci：0

• 获得价值wi：coins[i]

• 装满：初始化为-1

https://leetcode-cn.com/problems/coin-change/solution/yong-bei-bao-wen-ti-si-xiang-lai-li-jie-ying-bi-zh/

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        m = amount
        dp = [m+1]*(m+1)
        dp[0] = 0
        for c in coins:
            for j in range(m, c-1, -1):
                dp[j] = min(dp[j], dp[j-c]+1)
        return dp[-1] if dp[-1] != (m+1) else -1

377 组合总和 Ⅳ

• n件物品：nums

• 容量v：len(nums)

• 放入损耗ci：0

• 获得价值wi：num

• 不装满：初始化0

class Solution:
    def combinationSum4(self, nums: List[int], target: int) -> int:
        if not nums or target <= 0:
            return 0
        dp = [1]+[0]*target
        for i in range(1, target+1):
            for num in nums:
                if i >= num:
                    dp[i] += dp[i-num]
        return dp[-1]

Runtime: 40 ms, faster than 80.63% of Python3 online submissions for Combination Sum IV.

Memory Usage: 13.1 MB, less than 100.00% of Python3 online submissions for Combination Sum IV.

474 一和零

• n件物品：m个0、n个1

• 容量v：len(strs)

• 放入损耗ci：-1

• 获得价值wi：str

• 不装满：初始化0

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 item in strs:
            item0 = item.count('0')
            item1 = item.count('1')
            for i in range(m, item0-1, -1):
                for j in range(n, item1-1, -1):
                    dp[i][j] = max(dp[i][j], 1+dp[i-item0][j-item1])
        return dp[m][n]

Runtime: 3068 ms, faster than 71.04% of Python3 online submissions for Ones and Zeroes. Memory Usage: 12.8 MB, less than 100.00% of Python3 online submissions for Ones and Zeroes.

• 139

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        maxlen = 0
        for word in wordDict:
            if len(word) > maxlen:
                maxlen = len(word)
        res = [0]*len(s)
        for i in range(len(s)):
            p = i
            while p >= 0 and i-p <= maxlen:
                if (res[p] == 1 and s[p+1:i+1] in wordDict) or (p == 0 and
                                                                s[p:i+1] in wordDict):
                    res[i] = 1
                    break
                p -= 1
        return res[-1]

Runtime: 32 ms, faster than 96.24% of Python3 online submissions for Word Break.

Memory Usage: 12.8 MB, less than 100.00% of Python3 online submissions for Word Break.

494 目标和

• n件物品：所有正数num

• 容量v：(sum(nums)+S)//2

• 放入损耗ci：0

• 获得价值wi：num

• 不装满：初始化0

class Solution:
    def findTargetSumWays(self, nums: List[int], S: int) -> int:
        if sum(nums) < S or (sum(nums)+S) % 2 == 1:
            return 0
        v = (sum(nums)+S)//2
        dp = [1]+[0]*v
        for num in nums:
            for j in range(v, num-1, -1):
                dp[j] += dp[j-num]
        return dp[v]

Runtime: 72 ms, faster than 98.96% of Python3 online submissions for Target Sum.

Memory Usage: 12.9 MB, less than 100.00% of Python3 online submissions for Target Sum.

完全背包