python - 两种背包尺寸的多维成本0-1背包问题

Question

我正在查看 leetcode 上找到的此问题的解决方案.

问题指出:

Given an array, strs, with strings consisting of only 0s and 1s. Also two integers m and n.

Now your task is to find the maximum number of strings that you can form with given m 0s and n 1s. Each 0 and 1 can be used at most once.

Input: strs = ["10","0001","111001","1","0"], m = 5, n = 3

Output: 4

Explanation: This are totally 4 strings can be formed by the using of 5 0s and 3 1s, which are "10","0001","1","0".

用于解决该问题的算法如下:

def findMaxForm(strs, m, n):

    dp = [[0] * (n + 1) for _ in range(m +1)]
    
    for s in strs:
        
        zeros, ones = s.count('0'), s.count('1')
        
        for i in range(m, zeros - 1, -1):
            
            for j in range(n, ones -1, - 1):
                
                # dp[i][j] indicates it has i zeros ans j ones,
                # can this string be formed with those ?
                
                dp[i][j] = max( 1 + dp[i - zeros][j - ones], dp[i][j])
                
            # print(dp)
            
    return dp[-1][-1]

问题中令人困惑的部分是 dp[i][j] = max( 1 + dp[i - zeros][j - ones], dp[i][j]) 。我不确定这里发生了什么。为什么我们要从 0 中减去 i，从 1 中减去 j？

我还找到了一个图表，解释了 dp 表应如何查找数组中的每个元素。

我的问题:

• 第一个表代表什么？ x 轴和 y 轴？为什么有这么多1的。我想如果我理解了这一部分，可能会有所收获。如果有人浏览一下该图，我将不胜感激
• 为什么这种方式给我们的最大数量是0的和1可以成立吗？我想我对这部分仍然感到困惑dp[i][j] = max( 1 + dp[i - zeros][j - ones], dp[i][j]) .
• 此外，该解决方案被描述为“针对 2D 空间优化的 3d-DP:dp[j][k]:i 维度经过优化以就地使用。”这是什么意思？

Answer 1

当你遇到字符串s时，你基本上有两个选择。它要么属于最大解，要么不属于。

如果这样做，集合的大小会增加 1，但可供使用的 1 和 0 会减少。如果不使用它，集合的大小将保持不变，但保留 1 和 0 的数字也将保持不变。

表格dp代表了迄今为止对于“左”不同数量的1和0可以获得的最大此类集合。例如。 dp[m][n] 表示迄今为止使用 m 个 0 和 n 个 1 可以获得的最佳值。同样，对于 dp[2][3]，您可以使用 2 个零和 3 个 1 来表示其余字符串。

让我们把它包装在一起:

对于一些给定数量的零 (i) 剩余使用，以及一些给定数量的 1 (j) 剩余使用，以及字符串 s:

• 1 + dp[i - Zeros][j - Ones] 表示最大集合(如果您决定) 将 s 添加到集合中(这样您就剩下更少的 1 和 0)
• dp[i][j] 表示您不会采用此元素，并继续前进。

当您对两个值调用 max() 时，您基本上会说:我想要这两个选项中更好的一个。

我希望这能回答前两个问题，即为什么它是最大值以及 dp 线意味着什么。

---

Also the solution is described as a "3d-DP optimized to 2D space: dp[j][k]: i dimension is optimized to be used in-place." What does that mean?

在这里，你遇到了 3d 问题:字符串本身，你对其进行迭代 - 但你没有数组的另一个维度。您可以将其优化为就地，因为您始终只需要前一个字符串，而不需要比它“旧”的字符串，从而节省了宝贵的空间。