前兩天寫了 0-1 背包和完全背包，這兩種問題的差別是：物品可選取數量的限制。0-1 背包中，單件物品最多拿一次，所以只有取／不取兩種選擇。完全背包中，物品可以拿無限多次。

而多重背包則夾在兩個中間，每件物品有各自的數量上限。其實比較暴力的方式可以把多重背包拆成 0-1 背包，把重複的物品拆開來做 DP，這種類型的題目在 leetcode 上面好像還沒看到（如果有發現歡迎留言）。

474. Ones and Zeroes 這題我覺得還在 0-1 背包的範疇，不過限制是二維的（最基礎的背包問題限制只有一維）。解法也跟 0-1 背包差不多，第一個維度記可選取物品數量，後面的維度記限制，由這個方向出發可以一路推演到多維度 DP。

class Solution:
    def findMaxForm(self, strs: List[str], m: int, n: int) -> int:
        cnt = [[i.count("0"), i.count("1")] for i in strs]
        l = len(strs)

        mat = [[0 for _ in range(n+1)]for _ in range(m+1)]

        for a in range(l):
            weight_zero, weight_one = cnt[a]
            for b in range(m, weight_zero-1, -1):
                for c in range(n, weight_one-1, -1):
                        mat[b][c] = max(mat[b][c], mat[b-weight_zero][c-weight_one]+1)
        return mat[-1][-1]

• 0-1 背包
  • 474. Ones and Zeroes

• Total Count: 13