模版题-动态规划-一和零( 01背包 多维 )
- 版权声明：本站原创文章，于2026-05-15，由 管理员 发表。
- 转载请注明： 模版题-动态规划-一和零( 01背包 多维 ) | CodeGarden
**01背包问题中，背包可以是多维的。**
416. 分割等和子集 :给定背包容量，能不能装满这个背包。
1049. 最后一块石头的重量II :给定背包容量，尽可能装，最多能装多少
494. 目标和 :给定背包容量，装满背包有多少种方法。
474. 一和零 :给定背包容量，装满背包最多有多少个物品。
```python
class Solution:
# 给你一个二进制字符串数组 strs 和两个整数 m 和 n 。
# 请你找出并返回 strs 的最大子集的长度，该子集中 最多 有 m 个 0 和 n 个 1 。
# 如果 x 的所有元素也是 y 的元素，集合 x 是集合 y 的 子集 。
# 1 <= strs.length <= 600
# 1 <= strs[i].length <= 100
# strs[i] 仅由 '0' 和 '1' 组成
# 1 <= m, n <= 100
def findMaxForm(self, strs: List[str], m: int, n: int) -> int:
# 用 strs 装入 ( m,n )背包
# m个0 和 n个1 可以视作是二维的背包
# dp的含义: dp[ i ][ j ]表示容积为i个0和j个1的背包内包含的最大物品数
dp = [ [ 0 for _ in range( n + 1 ) ] for _ in range( m + 1 ) ]
for s in strs:
count_0 = 0
count_1 = 0
for v in s:
if v == '0': count_0 += 1
if v == '1': count_1 += 1
for i in range( m, count_0 - 1, -1 ):
for j in range( n, count_1 - 1, -1 ):
dp[ i ][ j ] = max( dp[ i ][ j ], dp[ i - count_0 ][ j - count_1 ] + 1 )
return dp[ m ][ n ]
```