具有两种背包尺寸的多维成本 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 table 应该如何查找数组中的所有元素。

我的问题：

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

Answer 1

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

如果这样做，集合的大小会增加 1，但剩下的 1 和 0 会减少。如果你不使用它，集合的大小保持不变，但如果留下 ones 和 zeros 的数字也是如此。

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

让我们总结一下：

对于一些给定数量的零 (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 问题：你迭代的字符串本身 - 但你没有数组的另一个维度。你优化它就地，因为你总是只需要前一个字符串，而不是比它“更老”的东西，节省你宝贵的 space.

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

multi-dimensional cost 0-1 knapsack problem with two backpack sizes

python

algorithm

knapsack-problem

dynamic-programming

data-structures