Find best pricing based on duration of booking using combination of products in PHP

Question

I have products based on different duration. For example, 1-hour booking is $200, 1 hour and 30 minutes is 280 and additional 30 minutes have $90. I have to find the best possible price according to the duration of the booking. [Minimum booking duration is 1 hour]

Product	Duration	Price
1 hr	60 min	$200
1 hr 30 m	90 min	$280
30 m	30 min	$90

*$90 for every additional 30 min which is not the perfect sum of 1 and 1hr 30mins hours

My Solution

1. Best scenario: If there is a product available for the booking duration, return that product.Eg:- 1 Hour booking

2. Normal Scenario: My solution was to find all unique combinations of products with a duration that has the perfect sum of the total duration. If there are unique combinations, sort the array in ascending order of total sum and the first combination will be the best price. Eg:- 2 Hour booking- We have two possible combinations 1 Hour * 2 = $400 or 1hr 30 min + 30min = $370. Second one best price

3. Worst Scenario: If there are no unique combinations find all possible combinations with repetition and sort the array to find the lowest price. An example case of the booking will be:- If customer books for 4 Hours there are a lot of possible combination

JS Code from This answer

function f(A, N, r=[], s=N){
  if (s == 0)
    return [r];

  result = [];

  for (let a of A)
    if (a <= s)
      result = result.concat(
        f(A, N, r.slice().concat(a), s-a));

  return result;
}

PHP Code from above JS Code:- [Edited - code not working as expected as js code]

protected function findCombination($products, $duration, $currentDuration, $resultTracker=[]){
    if ($currentDuration == 0)
      return $resultTracker;
    $result = [];      
    foreach ($products as $product){
        if ($product->duration <= $currentDuration){
            array_push($resultTracker,$product);
            array_push($result, $this->findCombination($products, $duration, ($currentDuration - $product->duration),$resultTracker) );
        }
    }
    return $result;
}

What is the best way to approach this problem? What is the best way to find combinations in PHP? Thanks in advance

Other StackOverflow questions

• Perfect Sum Problem with repetitions allowed

• Find all ways to sum given number (with repetitions allowed) from given set

• Generate combination of products given a total price limit

• Selecting A combination of minimum cost

• PHP find all combinations to a sum in inner array

Answer 1

Do it this way:

1. Sort bookings by highest duration/price ratio (descending order), so that the most convenient bookings are the first in the array;
2. Select the first booking whose duration is higher than minimum allowed duration and less than the target duration;
3. until you reach the target duration, push the first booking whose duration summed to the previous ones doesn't exceed the target duration, discarding higher absolute prices.

``

class Booking {
    public $name;
    public $duration;
    public $price;
    public $ratio;
    
    public function __construct($name, $duration, $price) {
        $this->name = $name;
        $this->duration = $duration;
        $this->price = $price;
        $this->ratio = $duration / $price;
    }
    
    public function __toString() {
        return $this->name.' ($'.$this->price.')';
    }
}

function findBest($bookings, $minBuyTime, $targetTime) {
    //Sort the bookings based on the duration/price ratio, in descending order (most convenient first)
    usort($bookings, function($a, $b) {
        if ($a->ratio < $b->ratio) return  1;
        if ($a->ratio > $b->ratio) return -1;
        return 0;
    });
    //echo implode(', ', $bookings),'<br/>';
    $result = array();
    $totalTime = 0;
    //Choose the first booking excluding the ones shorter than minBuyTime
    foreach ($bookings as $booking) {
        if ($booking->duration >= $minBuyTime) {
            $better = $booking;
            break;
        }
    }
    //If there is a cheaper booking then choose it (but still exclude the ones shorter than minBuyTime)
    $i = 0;
    while ($totalTime + $better->duration > $targetTime && ++$i < count($bookings)) {
        $booking = $bookings[$i];
        if ($booking->duration >= $minBuyTime && $booking->price < $better->price) $better = $booking;
    }
    $result[] = $better;
    $totalTime += $better->duration;
    //Add additional booking until the total time reaches the target time
    while ($totalTime < $targetTime) {
        $i = 0;
        $better = $bookings[0];
        while ($totalTime + $better->duration > $targetTime && ++$i < count($bookings)) {
            $booking = $bookings[$i];
            if ($booking->price < $better->price) $better = $booking;
        }
        $result[] = $better;
        $totalTime += $better->duration;
    }
    return $result;
}

Testing 3 different target durations with 3 different booking costs:

function test($bookings, $minBuyTime, $targetTime) {
    $best = findBest($bookings, $minBuyTime, $targetTime);
    $totalTime = 0;
    $totalPrice = 0;
    foreach ($best as $booking) {
        $totalTime += $booking->duration;
        $totalPrice += $booking->price;
    }
    echo $targetTime,' min: [',implode(', ', $best), '], ',$totalTime,' min - $',$totalPrice,'<br/>';
}

$minBuyTime = 60;
$bookings = array(
    new Booking('1 hr', 60, 200),
    new Booking('1 hr 30m', 90, 280),
    new Booking('30 m', 30, 90)
);
echo implode(', ', $bookings),'<br/>';
test($bookings, $minBuyTime, 60);
test($bookings, $minBuyTime, 120);
test($bookings, $minBuyTime, 240);
echo '<br/>';

$minBuyTime = 60;
$bookings = array(
    new Booking('1 hr', 60, 200),
    new Booking('1 hr 30m', 90, 250),
    new Booking('30 m', 30, 90)
);
echo implode(', ', $bookings),'<br/>';
test($bookings, $minBuyTime, 60);
test($bookings, $minBuyTime, 120);
test($bookings, $minBuyTime, 240);
echo '<br/>';

$minBuyTime = 60;
$bookings = array(
    new Booking('1 hr', 60, 200),
    new Booking('1 hr 30m', 90, 250),
    new Booking('30 m', 30, 110)
);
echo implode(', ', $bookings),'<br/>';
test($bookings, $minBuyTime, 60);
test($bookings, $minBuyTime, 120);
test($bookings, $minBuyTime, 240);
echo '<br/>';

The above will output:

1 hr ($200), 1 hr 30m ($280), 30 m ($90)
60 min: [1 hr ($200)], 60 min - $200
120 min: [1 hr 30m ($280), 30 m ($90)], 120 min - $370
240 min: [1 hr 30m ($280), 30 m ($90), 30 m ($90), 30 m ($90), 30 m ($90), 30 m ($90)], 240 min - $730

1 hr ($200), 1 hr 30m ($250), 30 m ($90)
60 min: [1 hr ($200)], 60 min - $200
120 min: [1 hr 30m ($250), 30 m ($90)], 120 min - $340
240 min: [1 hr 30m ($250), 1 hr 30m ($250), 30 m ($90), 30 m ($90)], 240 min - $680

1 hr ($200), 1 hr 30m ($250), 30 m ($110)
60 min: [1 hr ($200)], 60 min - $200
120 min: [1 hr 30m ($250), 30 m ($110)], 120 min - $360
240 min: [1 hr 30m ($250), 1 hr 30m ($250), 1 hr ($200)], 240 min - $700