1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
function knapsack(weights, values, capacity) {
  const n = weights.length;
  
  // Create a 1D array instead of 2D
  // dp[w] represents the maximum value that can be obtained
  // with a knapsack capacity of w
  const dp = Array(capacity + 1).fill(0);
  
  // Fill the array in a bottom-up manner
  for (let i = 0; i < n; i++) {
    // Important: iterate from right to left to avoid using the same item multiple times
    for (let w = capacity; w >= weights[i]; w--) {
      dp[w] = Math.max(dp[w], dp[w - weights[i]] + values[i]);
    }
  }
  
  // Return the maximum value
  return dp[capacity];
}
 
// Example usage:
const weights = [2, 3, 4, 5];
const values = [3, 4, 5, 6];
const capacity = 8;
console.log(knapsack(weights, values, capacity)); // Output: 10 (items with values 4 and 6)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
function longestCommonSubsequence(text1, text2) {
  const m = text1.length;
  const n = text2.length;
  
  // Ensure text1 is the shorter string to minimize space
  if (m > n) {
    return longestCommonSubsequence(text2, text1);
  }
  
  // Create two 1D arrays instead of a 2D array
  let prev = Array(m + 1).fill(0);
  let curr = Array(m + 1).fill(0);
  
  // Fill the arrays in a bottom-up manner
  for (let j = 1; j <= n; j++) {
    for (let i = 1; i <= m; i++) {
      if (text1[i - 1] === text2[j - 1]) {
        curr[i] = prev[i - 1] + 1;
      } else {
        curr[i] = Math.max(prev[i], curr[i - 1]);
      }
    }
    // Swap arrays for the next iteration
    [prev, curr] = [curr, prev];
  }
  
  // Return the length of LCS (result is in prev after the last swap)
  return prev[m];
}
 
// Example usage:
console.log(longestCommonSubsequence("abcde", "ace")); // Output: 3 (LCS is "ace")
console.log(longestCommonSubsequence("abc", "abc")); // Output: 3 (LCS is "abc")
console.log(longestCommonSubsequence("abc", "def")); // Output: 0 (no common subsequence)