Распределить число по ряду факторов (например, жадный алгоритм) ⇐ Php

[Anonymous]

Мне нужно найти стоимость доставки коробки, основываясь на ряде правил веса, подобных этому:

Код: Выделить всё

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

Таким образом, согласно этому массиву, доставка коробки весом 47 фунтов будет стоить 10,90 + 10,90 + 6,25 = 28,05 долларов США.
Это потому что 47 будет занимать в два раза больше диапазона (15-20] и один раз больше диапазона (5-10). ( обозначает символ уравнения >, а ] обозначает символ уравнения.
Сначала для простоты я создал промежуточный массив (верхних пределов каждого правила диапазонов) следующим образом (1 не имеет верхнего/нижнего значения). предел, но это легко исключить):

Код: Выделить всё

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

А затем я попытался распределить начальный вес по этому массиву аналогично процессу факторизации. Поэтому сначала я вообще проигнорировал нижние пределы и взял вес, т.е. 37,75 фунтов. Затем, используя следующий код, я создал массив «факторизации» каждого уровня веса:

Код: Выделить всё

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;
}

Что удобно, дало такой результат:

Код: Выделить всё

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

Затем я попробовал тот же код с весом 38 и понял свою первую ошибку... Есть некоторая проблема с крайним случаем, которую я пока не могу понять, для 38 по-прежнему добавляет +1 к правилу 1 уровня.
Затем я попробовал 47,75 фунтов и обнаружил вторую ошибку... Как я уже сказал, для простоты я использовали верхние пределы, что мешает «факторизации» веса. Итак, для веса 47,75 фунтов приведенный выше код выдал такой результат:

Код: Выделить всё

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

что совершенно неверно, поскольку 1-й уровень нельзя использовать 8 раз, поскольку 8 (или 7,99, если быть точным) попадает в диапазон (5-10].
В целом, к сожалению, мой подход во многом ошибочен. Может кто-нибудь помочь мне найти правильный код для решения этой проблемы?

Подробнее здесь: https://stackoverflow.com/questions/783 ... -algorithm