Topic describes

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

Find and return the size of the largest subset of STRS that has at most m zeros and n ones.

If all members of x are also members of y, the set x is a subset of the set y.

 

Example 1:

Input: STRS = [” 10 “, “0001”, “111001”, “1”, “0”], m = 5, n = 3 output: 4: The largest subset with at most five zeros and three ones is {“10″,”0001″,”1″,”0”}, so the answer is 4. Other smaller subsets that satisfy the meaning of the question include {“0001″,”1”} and {“10″,”1″,”0”}. {“111001”} does not satisfy the meaning of the question, because it contains four 1’s and the value 3 is greater than n. 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.

Tip:

1 <= strs.length <= 600 1 <= STRS [I]. Length <= 100 STRS [I] 1 <= m, n <= 100

Source: LeetCode link: leetcode-cn.com/problems/on… Copyright belongs to collar network. Commercial reprint please contact the official authorization, non-commercial reprint please indicate the source.

Their thinking

01 Backpack problem 🎒;

01 backpack 🎒 problem is characterized by each item only one, its choice to put in the backpack or choose not to put in the backpack 🎒;

In this case, each element of STRS is considered a commodity; However, there is only one backpack 🎒 and its capacity is m and N. Both dimensions satisfy the maximum capacity under the condition. Therefore, the maximum solution type of the knapsack problem is 01. Dynamic programming tetralogy:

  • Determine the meaning of DP:
    • Dp [I][j] represents the largest subset of STRS satisfying at most I zeros and J ones
  • Determine the recursion formula:
    • We assume that the last STRS element of dp[I][j] +1 is substr, and substr now has x zeros and y ones;
    • Dp [I][j] can be derived from dp[i-x][j-y]+1;
    • Then the result dp[I][j] is compared with dp[i-m][j-n]+1. Take the maximum value;
    • Dp [I][J]=Math. Max (dp[I][J],p[i-m][j-n]+1);
    • Dp [j]= math.max (dp[j],dp[j-weight[I]]+value[I])
    • The x and y of the string substr correspond to the weight of the item (weight[I]), and the number of strings themselves corresponds to the value of the item (value[I]).
  • Dp array initialization;
    • 01 backpack problem 🎒, item value will not be negative, dp array initialized to 0; Used on a recursive basis;
  • Traversal order:
    • 01 backpack must be the outer for loop traversing items, the inner for loop traversing backpack capacity and traversing from back to front!

code

/ * * *@param {string[]} strs
 * @param {number} m
 * @param {number} n
 * @return {number}* /
var findMaxForm = function(strs, m, n) {
    // This is a variant of the 01 backpack problem. Choose or not to put the backpack 🎒
    // define dp:dp[I][j] to indicate the number of subsets consisting of at most I zeros and J ones;
        // In this case, the elements in STRS are equivalent to items. The capacity of the backpack 🎒 is the condition that both dimensions I and J satisfy at the same time.
        / / sure 01 knapsack problem 🎒 recurrence formula dp [j] = math.h Max (dp) [j], dp [j - wight [I]] + value [I])
        So at this moment / / recursive formula should be: dp [I] [j] = math.h Max (dp [I] [j], dp [I - zeroNum] [j - oneNum] + 1)
        
        // 1, count each string element (item) dimensions I, j capacity;
        let map=new Map(a);for(let item of strs){
            let oneNum=0;
            for(let char of item){
                if(char==='1'){
                    oneNum++
                }
            }// end of for
            map.set(item,[item.length-oneNum,oneNum])
        }
        // 2. Complete the statistics of the capacity of the two dimensions I and J, build the TWO-DIMENSIONAL array dp, and initialize 0;
        const dp=new Array(m+1)
        for(let i=0; i<(m+1); i++){ dp[i]=new Array(n+1).fill(0);
        }
        // 3.
        const N=strs.length;
        // Iterate over the items
        for(let i=0; i<N; i++){/ * * * * * * * * * * * * * * * * * * *
            let [v0,v1]=map.get(strs[i])
            for(letj=m; j>=v0; j--){for(letk=n; k>=v1; k--){ dp[j][k]=Math.max(dp[j][k],dp[j-v0][k-v1]+1); }}// end of m n
        }// end of for
        return dp[m][n]
};
Copy the code

Complete backpack 🎒 problem

【 Review the old and learn the new 】322. ChangeAnimation demonstration – minimum solution of complete knapsack problem – dynamic programming implementation

【 Review the old and learn the new 】518. Change for IICombined solution of complete knapsack problems-implementation of dynamic programming

【 Review the old and learn the new 】377. Combination sum ⅳPermutation solution of complete knapsack problems-implementation of dynamic programming