Javascript Question posted in
A very good W3school tutorial can be found here.

Javascript – 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"
Tags:

2

Answers


  1. 0

    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));
    Login or Signup to reply.
  2. 0

    This is how you can use backtracking for your benefit in this case, treating each fruit as a binary question of whether you add them to the cart or not (except the case when there are not enough funds, when we are forced not to add them)

    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.log(bestSofar.map(item => item.title));
bestSofar = [];
findCombination(products, 0, 800000); // Banana, Orange, Strawberry and Grape
console.log(bestSofar.map(item => item.title));
bestSofar = [];
findCombination(products, 0, 300000); // Banana and Orange
console.log(bestSofar.map(item => item.title));
bestSofar = [];
findCombination(products, 0, 20000); // Nothing
console.log(bestSofar.map(item => item.title));
    Login or Signup to reply.
Please signup or login to give your own answer.

Back To Top
Search