สร้างสตริงจาก 0 และ 1 ภายใต้ข้อจำกัดจำนวน (Forming Strings with 0s and 1s) ใน JavaScript

ปัญหา

รับอาร์เรย์สตริง arr (ประกอบ 0,1) และ m, n หาจำนวนสตริงใน arr ที่สร้างได้โดยใช้ 0 ไม่เกิน m ตัว และ 1 ไม่เกิน n ตัว

ตัวอย่าง

const arr = ["10", "0001", "111001", "1", "0"]; const m = 5, n = 3;

สร้างได้ 4 สตริง: "10", "0001", "1", "0" → 4

โค้ดตัวอย่าง (0/1 Knapsack DP)

const arr = ["10", "0001", "111001", "1", "0"]; const m = 5, n = 3; 
const findAllStrings = (arr = [], m = 1, n = 1) => { 
  const getCount = str => str.split('').reduce((acc, cur) => { cur === '0' ? acc.zeros++ : acc.ones++; return acc; }, {zeros:0, ones:0}); 
  const dp = Array.from({length: m+1}, () => Array(n+1).fill(0)); 
  for(let i = 0; i < arr.length; i++) { 
    const {zeros, ones} = getCount(arr[i]); 
    for(let j = m; j >= zeros; j--) { 
      for(let k = n; k >= ones; k--) { 
        dp[j][k] = Math.max(dp[j-zeros][k-ones]+1, dp[j][k]); 
      } 
    } 
  } 
  return dp[m][n]; 
}; 
console.log(findAllStrings(arr, m, n));

ผลลัพธ์

4