dp/knapsack-problem/ones-and-zeroes

Ones and Zeroes

描述

You are given an array of binary strings strs and two integers m and n.

Return the size of the largest subset of strs such that there are at most m 0's and n 1's in the subset.

A set x is a subset of a set y if all elements of x are also elements of y.

Example 1:

Input: strs = ["10","0001","111001","1","0"], m = 5, n = 3
Output: 4
Explanation: The largest subset with at most 5 0's and 3 1's is {"10", "0001", "1", "0"}, so the answer is 4.
Other valid but smaller subsets include {"0001", "1"} and {"10", "1", "0"}.
{"111001"} is an invalid subset because it contains 4 1's, greater than the maximum of 3.

Example 2:

Input: strs = ["10","0","1"], m = 1, n = 1
Output: 2
Explanation: The largest subset is {"0", "1"}, so the answer is 2.

Constraints:

• 1 <= strs.length <= 600
• 1 <= strs[i].length <= 100
• strs[i] consists only of digits '0' and '1'.
• 1 <= m, n <= 100

分析

0-1 背包问题，每个字符串有两种重量，0 的个数和 1 的个数，每个字符串的价值都是 1，因此这个问题里有两个背包，一个装 0，一个装 1，价值则是背包里字符串的个数。

令f[i][j][k]表示把前i个字符串装进容量为j的背包 0 和容量为k背包 1，可以获得的最大集合的大小，则状态转移方程是：

$$f[i][j][k]=\max\left{f[i-1][j][k], f[i-1][j-w_0[i][k-w_1[i]]+1\right}$$

代码

# TODO

// Ones and Zeroes
// 0-1 knapsack problem
// Time Complexity: O(l*m*n), Space Complexity: O(m*n)
class Solution {
    public int findMaxForm(String[] strs, int m, int n) {
        int[][] f = new int[m+1][n+1];

        int[] w0 = new int[strs.length];
        int[] w1 = new int[strs.length];
        for (int i = 0; i < strs.length; ++i) {
            w0[i] = numberOfZeroes(strs[i]);
            w1[i] = strs[i].length() - w0[i];
        }

        for (int i = 0; i < strs.length; ++i) {
            for(int j = m; j >= w0[i]; --j)
                for(int k = n;k >= w1[i]; --k) {
                    f[j][k] = Math.max(f[j][k], f[j-w0[i]][k-w1[i]]+1);
                }
        }
        return f[m][n];
    }

    private static int numberOfZeroes(String s) {
        int count = 0;
        for (char c : s.toCharArray()) {
            if (c == '0') count++;
        }
        return count;
    }
}

// TODO