MySQL generate random product list based on budget?

Question

I'm tinkering with a function to enable users to specify a budget, and have them receive a list of randomly picked products that add up as best as possible to their specified budget.

As it stands now, I'm trying to do this with PHP but it tends to slow down when there is a huge product list.

Is this at all possible with just a MySQL query?

Edit:

My PHP "implementation":

$budget = 100;
$spent = 0;
$finished = false;

while(!$finished) {

    $getRandomProduct = mysql_query('SELECT `id`, `price` FROM `products` WHERE `price` <= "'.($budget-$spent).'" ORDER BY RAND() LIMIT 1');
    if(mysql_num_rows($getRandomProduct)) {
        $randomProduct = mysql_fetch_assoc($getRandomProduct);
        $productList[] = $randomProduct['id'];
        $spent += $randomProduct['price'];
    } else {
        $finished = true;
    }
}

What do you mean by "as best as possible"? This sounds like an NP-complete problem, which would be hard to implement in either PHP or MySQL. Can you give some examples? — Gordon Linoff, Nov 04 '14 at 20:33
By best as possible I mean as close to the budget as possible, I'll add what I have now — Matt, Nov 04 '14 at 20:37
. . This is a variant of the bin-packing problem, which is actually NP-hard. There is no known fast way to get the "best" solution, without evaluating basically all the possibilities. If you find a better way, you'll have an algorithm named after you. — Gordon Linoff, Nov 04 '14 at 20:45
As others have noted, what you have asked is a very difficult task to achieve, before you even start thinking about PHP vs. MySQL, you need to think about what algorithm you want to go with to solve the problem. For example is a combination of an item price 99 along with an item price 1 better than 100 items priced 1? There seems to be incongruity with your desires for "best" and "random". I don't think you can have both. — Mike Brant, Nov 04 '14 at 20:48
Thank you both for your comments, now I understand this problem a lot better. I've added more "randomness" by making the available price for the next query randomly generated by having the available sum as the max and 0.01 as the minimum. — Matt, Nov 04 '14 at 21:05

score 0 · Answer 1 · answered Dec 11 '18 at 16:31

The performance and the "randomness" of the result set can be further improved if you first define how many products to include.

$min = 10;
$max = 20;
$total = rand($min,$max);

The algorithm is based on the following:

In a collection of n positive numbers that sum up to S, at least one of them will be less than S divided by n (S/n)

Steps:

Select a product randomly where price < BUDGET /TOTAL. Get its price, lets say X.
Select a product randomly where price < (BUDGET - X)/(TOTAL - 1). Get its price, assume Y.
Select a product randomly where price < (BUDGET - X - Y)/(TOTAL - 2).

Repeat this and get (TOTAL - 1) products. For the last product, select one where price = remaining price. (or price <= remaining price and order by price desc and hopefully you could get close enough).

$budget = 100;
$spent = 0;
$finished = false;

for($i = 0; $i < $total - 1; $i++) {
    $getRandomProduct = mysql_query('SELECT `id`, `price` FROM `products` WHERE `price` <= "'.(($budget-$spent)/($total - $i)).'" ORDER BY RAND() LIMIT 1');
    if(mysql_num_rows($getRandomProduct)) {
        $randomProduct = mysql_fetch_assoc($getRandomProduct);
        $productList[] = $randomProduct['id'];
        $spent += $randomProduct['price'];
    } else {
        break;
    }
}
$getRandomProduct = mysql_query('SELECT `id`, `price` FROM `products` WHERE `price` <= "'.($budget-$spent).'" ORDER BY `price` DESC LIMIT 1');
$productList[] = $randomProduct['id'];

This improves:

The query performance, the condition is more strict
The result set is more random, as previous you could easily select the 1st product close to the budge and limit the budget of the others

References:

My answer using the same algorithm for another question

MySQL generate random product list based on budget?

1 Answers1