Алгоритм в PHP, чтобы выбрать подмножество первых ровно N элементов, которые складываются в X порог
Это вход:
$deals = array(
array('deal' => '1', 'deal_date' => '2017-02-13', 'amount' => '400'),
array('deal' => '2', 'deal_date' => '2017-04-17', 'amount' => '8900'),
array('deal' => '3', 'deal_date' => '2017-04-23', 'amount' => '1000'),
array('deal' => '4', 'deal_date' => '2017-06-02', 'amount' => '2400'),
array('deal' => '5', 'deal_date' => '2017-07-05', 'amount' => '10500'),
);
Я ищу подмножество из ровно N элементов, в которых сумма свойств ‘amount’ больше или равна X, а элементы имеют наименьшее возможное свойство ‘deal_date’.
Если нет подмножества, которое соответствует правилам:
$subset = false;
Таким образом, для N = 2 и X = 10000 я получаю этот вывод:
$subset = array(
array('deal' => '2', 'deal_date' => '2017-04-17', 'amount' => '8900'),
array('deal' => '4', 'deal_date' => '2017-06-02', 'amount' => '2400'),
);
для N = 3 и X = 12000:
$subset = array(
array('deal' => '2', 'deal_date' => '2017-04-17', 'amount' => '8900'),
array('deal' => '3', 'deal_date' => '2017-04-23', 'amount' => '1000'),
array('deal' => '4', 'deal_date' => '2017-06-02', 'amount' => '2400'),
);
Моя текущая идея заключается в создании массива, который содержит массивы списка сделок в каждом мыслимом порядке. Затем я просматриваю их, чтобы найти список сделок, которые соответствуют критериям, но затем у меня есть список сделок, и я не уверен, как определить «самую раннюю».
Я также ищу алгоритм с наименьшей временной сложностью.
Любые идеи были бы хорошы.
Решение
Это не просто, но примерно это
Там будет лучший способ.
Примерный источник
$calculate = 0;
$end_case = array();
$sum = 10000;
// first amount 10000 over value array remove
foreach($deals as $key => $val){
if($val['amount']>=$sum)unset($deals[$key]);
}
// second Obtaining data
foreach($deals as $key => $val){
foreach($deals as $k => $v){
// same deal excetpion
if($val['deal']==$v['deal']) continue;
$calc = deal_sum($val['amount'],$v['amount']);
if($calc>=$sum){
echo "#".$v['deal']." => ".$val['amount']."+".$v['amount']." = ".$calc."\n";
array_push($end_case,$v['deal']);
}
print_r($end_case);
}
}
function deal_sum($source,$destination){
$result = $source+$destination;
return $result;
}
Другие решения
Вы должны иметь в виду сложность времени вашего алгоритма, иначе большие входные наборы будут длиться вечно.
Алгоритм для N:
Возвращает array () первых сделок $ number_of_deals_to_combine из
$ сделок, заказанных ‘deal_date’, которые имеют порог не менее $ или
большие объединенные суммы или false, если такая комбинация не найдена.
Использует скользящее окно из элементов $ number_of_deals_to_combine
исключая сделки, которые имеют слишком маленькую сумму.
function combine_deals($deals, $threshold, $number_of_deals_to_combine){
$return = false;
//are there enough deals to combine?
if(count($deals) >= $number_of_deals_to_combine){
//are deals sorted by date? sort them
usort($deals,function($a, $b){return strnatcmp($a['deal_date'],$b['deal_date']);});
//find out if there is a possible solution, by adding up the biggest deals
$amounts = array_map('intval',array_column($deals,'amount'));
rsort($amounts); //sort descending
if(array_sum(array_slice($amounts, 0, $number_of_deals_to_combine)) >= $threshold){
//find the smallest possible number that is part of a solution
$min_limit = $threshold - array_sum(array_slice($amounts, 0, $number_of_deals_to_combine - 1));
//rolling window
$combined = array();
foreach($deals as $deal){
if(intval($deal['amount']) < $min_limit){continue;} //this deal is not part of any solution
$combined[] = $deal;
//keep the number of deals constant
if(count($combined) > $number_of_deals_to_combine){
$combined = array_slice($combined, count($combined) - $number_of_deals_to_combine);
}
//there are enough deals to test
if(count($combined) == $number_of_deals_to_combine){
$amount = array_sum(array_map('intval',array_column($combined, 'amount')));
if($amount >= $threshold){
$return = $combined;
break;
}
}
}
}
}
return $return;
}
$threshold = 10000;
$number_of_deals_to_combine = 2;
$result = combine_deals($deals, $threshold, $number_of_deals_to_combine);
Поля суммы всегда целые? Если нет, замените весь intval везде на floatval.