সমস্যা
আমাদের একটি জাভাস্ক্রিপ্ট ফাংশন লিখতে হবে যা ০ ও ১ দিয়ে বানানো স্ট্রিংগুলোর একটি অ্যারে arr প্রথম আর্গুমেন্ট হিসেবে নেবে। دومা ও তৃতীয় আর্গুমেন্ট হিসেবে দুটি সংখ্যা m ও n নেবে। ফাংশনটি বের করবে arr-তে থেকে কতগুলো স্ট্রিং সর্বোচ্চ m টি ০ এবং n টি ১ ব্যবহার করে তৈরি করা যায়।
উদাহরণ:
const arr = ["10", "0001", "111001", "1", "0"]; const m = 5, n = 3;
আউটপুট হবে:
const output = 4;
আউটপুট ব্যাখ্যা:
মোট ৪টি স্ট্রিং বানানো যায় ৫টি ০ ও ৩টি ১ দিয়ে: "10", "0001", "1", "0"
উদাহরণ
কোডটি নিচের মতো (0/1 ন্যাপস্যাক / 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
