Как найти оптимальные продукты с наименьшей ценой и наибольшим количеством?

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.info(findOptimalProductsDP(products, 1000000));
console.info(findOptimalProductsDP(products, 800000));
console.info(findOptimalProductsDP(products, 300000));
console.info(findOptimalProductsDP(products, 200000));

const products = [
    {
        "title": "Apple",
        "quantity": "+2140",
        "price": "800000"
    },
    {
        "title": "Orange",
        "quantity": "+1440",
        "price": "200000"
    },
    {
        "title": "Banana",
        "quantity": "900",
        "price": "70000"
    },
    {
        "title": "Grape",
        "quantity": "96",
        "price": "90000"
    },
    {
        "title": "Strawberry",
        "quantity": "800",
        "price": "130000"
    },
];

let bestSofar = [];

function findCombination(products, index, funds, combination = []) {
    if (index < products.length) {
        findCombination(products, index + 1, funds, combination);
        if (funds >= products[index].price) {
            findCombination(products, index + 1, funds - products[index].price, combination.concat(products[index]));
        }
    } else {
        if (combination.map(item => item.quantity * item.price).reduce((a, b) => a + b, 0) > bestSofar.map(item => item.quantity * item.price).reduce((a, b) => a + b, 0)) {
            bestSofar = combination;
        }
    }
}



bestSofar = [];
findCombination(products, 0, 1000000); // Banana, Orange, Strawberry and Grape
console.info(bestSofar.map(item => item.title));
bestSofar = [];
findCombination(products, 0, 800000); // Banana, Orange, Strawberry and Grape
console.info(bestSofar.map(item => item.title));
bestSofar = [];
findCombination(products, 0, 300000); // Banana and Orange
console.info(bestSofar.map(item => item.title));
bestSofar = [];
findCombination(products, 0, 20000); // Nothing
console.info(bestSofar.map(item => item.title));