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"
2
Answers
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:
dp to store the maximum total quantity achievable for each
combination of products and budgets.
budget.
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.
the function backtracks to determine which products were selected
within the given budget.
products and the total quantity achieved within the given budget.
Code:
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)