Calculate shipping cost by weight using an array of tiered price

ghz 8months ago ⋅ 99 views

I need to find the cost to ship a box, based on an array of weight rules, similar to this:

$rules = [
    '1'     => '1.2',
    '5-10'  => '6.25',
    '10-15' => '9.2',
    '15-20' => '10.9',
];

The goal is to optimize the result so that the fewest number of rules are used with the lowest possble cost.

For a box that weighs 47 lbs, these sets of rules would technically reach the weight:

  • (1)x47
  • (5-10)x5
  • (10-15)x3,(1)x2
  • (15-20)x3
  • (15-20)x2,(10-15)x1
  • (15-20)x2,(5-10)x1
  • etc.

The best/desired pricing calculation would be (15-20) $10.90 + (15-20) $10.90 + (5-10) $6.25 = $28.05 USD to ship. This is the sum of the cheapest combination of prices.

At first, for simplicity, I created an intermediate array (of the upper limits of each ranges rule) like this (1 doesn't have an upper/lower limit, but that's easy to exclude):

$tiers = [
    20,
    15,
    10,
    1,
];

And then I tried to distribute the initial weight to that array in a way similar to a factorization process. So at first I totally ignored the lower limits, and took a weight, ie. 37.75 lbs. Then, using the following code, I produced the "factorization" array of each weight tier:

print_r( distribute( 37.75 );

function distribute( $weight = 0 ) {
    $tiers = [1, 10, 15, 20];

    rsort( $tiers );

    foreach ( $tiers as $tier ) {
        $counters[$tier] = 0;
    }

    foreach ( $tiers as $tier ) {
        $quotient  = $weight / $tier;
        $floored   = floor( $quotient );
        $remaining = $weight - $floored * $tier;

        if ( $quotient >= 1 && $remaining > 1 ) {
            $counters[$tier] = $floored;
            $weight          = $remaining;
        } else if ( $tier == 1 ) {
            $counters[$tier] = ( $floored + 1 );
            $weight          = $weight - ( $floored + 1 ) * $tier;
        }
    }

    return $counters;
}

Which conveniently produced an output like this:

    Array (
        [20] => 1
        [15] => 1
        [10] => 0
        [1] => 3
    )

Then, I tried the same code with weight 38, and realized my first mistake... There is some problem with an edge case that I can't figure out yet, that for 38 still adds a +1 to the 1-tier rule.

Then, I tried 47.75 lbs, and found the second mistake... As I said, for simplicity, I used the upper limits, which messes with the "factorization" of a weight. So, for 47.75 lbs, the above code produced an output like this:

    Array (
        [20] => 2
        [15] => 0
        [10] => 0
        [1] => 8
    )

which is totally wrong, as consuming 1-tier 8 times is not the most economical path.

All in all, unfortunately, my approach is flawed in many ways. Can someone help me please figure out the correct code to deal with this problem?

Answers

It seems like you're trying to solve the problem of finding the optimal combination of weight rules to minimize the shipping cost for a given weight. This problem is similar to the knapsack problem, where you need to find the best combination of items (in this case, weight rules) to maximize or minimize a value (in this case, shipping cost) while staying within a weight constraint (the weight of the box).

One approach to solving this problem is by using dynamic programming. Here's a Python implementation to find the minimum shipping cost for a given weight using the provided weight rules:

def min_shipping_cost(weight, rules):
    # Initialize a table to store the minimum cost for each weight
    dp = [float('inf')] * (weight + 1)
    dp[0] = 0  # Base case: minimum cost for weight 0 is 0

    for w in range(1, weight + 1):
        for rule in rules:
            # Split the rule into lower and upper bounds
            lower, upper = map(int, rule.split('-'))

            # Check if the current weight falls within the rule bounds
            if lower <= w <= upper:
                # Update the minimum cost for the current weight
                dp[w] = min(dp[w], float(rules[rule]) + dp[w - lower])

    return dp[weight]

# Example usage:
weight = 47
rules = {
    '1': '1.2',
    '5-10': '6.25',
    '10-15': '9.2',
    '15-20': '10.9',
}
result = min_shipping_cost(weight, rules)
print(f"The minimum shipping cost for a weight of {weight} lbs is ${result:.2f}")

This implementation uses dynamic programming to compute the minimum shipping cost for each weight from 1 to the given weight. It iterates through each weight rule and updates the minimum cost for each weight using the formula dp[w] = min(dp[w], cost_of_rule + dp[w - lower_bound]).

This approach should correctly find the optimal combination of weight rules to minimize the shipping cost for the given weight.

#php