How to find the optimal products with the lowest price amount with the highest quantity?

I tried to write a function for myself but it somehow incorrectly outputs the final result:

function findOptimalProducts(products, budget) {
    const getPrice = (priceString) => parseFloat(priceString.replace(/,/g, ""));
    const getQuantity = (quantityString) => parseFloat(quantityString.slice(1).replace(/K/g, "")) * (quantityString.endsWith("K") ? 1000 : 1);

    // Sort products by price per unit (price / quantity) in ascending order
    products.sort((a, b) => {
        const quantityA = getQuantity(a.quantity);
        const quantityB = getQuantity(b.quantity);
        const priceA = getPrice(a.price);
        const priceB = getPrice(b.price);
        return (priceA / quantityA) - (priceB / quantityB);
    });

    let selectedProducts = [];
    let totalQuantity = 0;
    let totalPrice = 0;

    // Loop through sorted products
    for (const product of products) {
        const pricePerUnit = getPrice(product.price) / getQuantity(product.quantity);
        const quantity = getQuantity(product.quantity);
        const productCost = pricePerUnit * quantity;

        // Check if adding the product would exceed the budget
        if (totalPrice + productCost <= budget) {
            selectedProducts.push(product);
            totalQuantity += quantity;
            totalPrice += productCost;
        } else {
            // Budget reached or almost reached (within a small tolerance), continue iterating
            if (totalPrice + productCost > budget + 100) { // Adjust tolerance as needed
                continue;
            }
        }
    }

    return {
        selectedProducts,
        totalQuantity,
        totalPrice,
    };
}

const products = [
    {
        "title": "Apple",
        "quantity": "+2.14K",
        "price": "800,000"
    },
    {
        "title": "Orange",
        "quantity": "+1.44K",
        "price": "200,000"
    },
    {
        "title": "Banana",
        "quantity": "+900",
        "price": "70,000"
    },
    {
        "title": "Grape",
        "quantity": "+96",
        "price": "90,000"
    },
    {
        "title": "Strawberry",
        "quantity": "+800",
        "price": "130,000"
    },
];



findOptimalProducts(products, 1000000); // Banana, Orange, Strawberry and Grape
findOptimalProducts(products, 800000); // Banana, Orange, Strawberry and Grape
findOptimalProducts(products, 300000); // Banana and Orange
findOptimalProducts(products, 20000); // Nothing

How can I correctly find products whose price sum is the lowest with the highest quantity?

Example correct results:

Budget: $1M
Result: "Apple", "Banana" and "Strawberry"

Budget: $800K
Result: "Orange", "Banana", "Grape" and "Strawberry"

Budget: $300K
Result: "Orange" and "Banana"

Budget: $200K
Result: "Banana" and "Strawberry"

Description:

The findOptimalProductsDP function aims to efficiently determine the optimal combination of products to purchase within a given budget. It utilizes dynamic programming to solve the problem in a time-efficient manner.

How it Works:

1. Dynamic Programming Array Initialization: It initializes a 2D array dp to store the maximum total quantity achievable for each combination of products and budgets.
2. Base Case: Sets up the base case where no products are used with any budget.
3. Iterating through Products and Budgets: The function iterates through each product and each possible budget, calculating the maximum quantity achievable for each combination by considering whether to include or exclude the current product.
4. Backtracking: After computing the maximum quantity for each budget, the function backtracks to determine which products were selected within the given budget.
5. Output: Finally, it returns an object containing the selected products and the total quantity achieved within the given budget.

Code:

function findOptimalProductsDP(products, budget) {
  // Utility functions to extract price and quantity
  const getPrice = (priceString) => parseFloat(priceString.replace(/,/g, ""));
  const getQuantity = (quantityString) => parseFloat(quantityString.slice(1).replace(/K/g, "")) * (quantityString.endsWith("K") ? 1000 : 1);

  const n = products.length;
  // Initialize DP array
  const dp = Array(n + 1).fill(0).map(() => Array(budget + 1).fill(0));

  // Base case: No products used with any budget
  for (let j = 0; j <= budget; j++) {
    dp[0][j] = 0;
  }

  // Iterate through products and budgets
  for (let i = 1; i <= n; i++) {
    const product = products[i - 1];
    const price = getPrice(product.price);

    for (let j = 0; j <= budget; j++) {
      if (price > j) {
        // If the price of the product exceeds the budget, exclude the product
        dp[i][j] = dp[i - 1][j]; // Exclude product
      } else {
        const remainingBudget = j - price;
        const maxQuantityWithRemaining = dp[i - 1][remainingBudget];
        const totalQuantity = maxQuantityWithRemaining + getQuantity(product.quantity);
        // Max of excluding or including the current product
        dp[i][j] = Math.max(dp[i - 1][j], totalQuantity);
      }
    }
  }

  // Backtrack to find selected products
  const selectedProducts = [];
  let remainingBudget = budget;
  for (let i = n; i > 0 && remainingBudget > 0; i--) {
    if (dp[i][remainingBudget] !== dp[i - 1][remainingBudget]) {
      selectedProducts.push(products[i - 1]);
      remainingBudget -= getPrice(products[i - 1].price);
    }
  }

  return {
    selectedProducts,
    totalQuantity: dp[n][budget],
  };
}


const products = [{
    "title": "Apple",
    "quantity": "+2.14K",
    "price": "800,000"
  },
  {
    "title": "Orange",
    "quantity": "+1.44K",
    "price": "200,000"
  },
  {
    "title": "Banana",
    "quantity": "+900",
    "price": "70,000"
  },
  {
    "title": "Grape",
    "quantity": "+96",
    "price": "90,000"
  },
  {
    "title": "Strawberry",
    "quantity": "+800",
    "price": "130,000"
  },
];

console.log(findOptimalProductsDP(products, 1000000));
console.log(findOptimalProductsDP(products, 800000));
console.log(findOptimalProductsDP(products, 300000));
console.log(findOptimalProductsDP(products, 200000));