findMaxForm

Leetcode

给出一个数组，两个整数，数组里的元素是0和1组合的字符串。两个整数代表拥有的0和1的个数，要求用已有的0和1，凑出数组里有de

该问题是变式的0-1背包问题，只不过其背包空间是二维的。那么再加上物品，这是一个三维空间的背包问题。但是，可以从利用基本0-1背包问题空间优化时的思路，将物品那一维省略，用一张二维表记录当前背包载重的价值。其中：行数的0的个数，列数是1的个数。

'''
# File: findMaxForm.py
# Author: 0HP
# Date: 202002110
# Purpose: solve the problem in website: https://leetcode.com/problems/ones-and-zeroes/
'''
class Solution:
    def findMaxForm(self, strs, m: int, n: int) -> int:
        #build the space of bag which has 2 orders
        #row is n,col is m
        dp=[[0 for i in range(n+1)]for j in range(m+1)]
        for i in strs:
            zeros,ones,zero,one=m,n,0,0
            for j in i:
                if j=="1":#"1"'s counts
                    one+=1
                if j=="0":#"0"'s counts
                    zero+=1
            while not zeros<zero:
                ones=n
                while not ones<one:
                    dp[zeros][ones]=max(dp[zeros][ones],dp[zeros-zero][ones-one]+1)
                    ones-=1
                zeros-=1
        return dp[-1][-1]