Сделал что-то похожее на это в личном проекте, но в php-коде.
Если вы хотите портировать на c #, не стесняйтесь.
Этот код учитывает возможность совпадения нескольких комбинаций, поэтому возвращаемое значение будет массивом x лучших результатов.
ПРИМЕЧАНИЕ. При этом учитывается, что любой элемент можно использовать 0 или 1 раз в каждом результате
<code><?php
$products = [
['id' => 1, 'price' => 3.00, 'energy' => 200],
['id' => 2, 'price' => 14.10, 'energy' => 3200],
['id' => 3, 'price' => 2.66, 'energy' => 300],
['id' => 4, 'price' => 5.00, 'energy' => 450],
['id' => 5, 'price' => 6.23, 'energy' => 667],
['id' => 6, 'price' => 7.00, 'energy' => 1200]
];
function genCombinations($values, $count = 0)
{
// Figure out how many combinations are possible:
$comboCount = pow(count($values) , $count);
$r = [];
// Iterate and add to array
for ($i = 0; $i < $comboCount; $i++){
$r[] = getCombination($values, $count, $i);
}
return $r;
}
// State-based way of generating combinations:
function getCombination($values, $count, $index)
{
$result = [];
for ($i = 0; $i < $count; $i++) {
// Figure out where in the array to start from, given the external state and the internal loop state
$pos = $index % count($values);
// Append and continue
$result[] = $values[$pos];
$index = ($index - $pos) / count($values);
}
return $result;
}
//maximize energy for given price
function getBestProductCombinations($products,$price_limit){
//find all combinations where each product is either selected or not - true or false
$combos = genCombinations([true,false],count($products));
$results = [];
foreach($combos as $combo){
//loop through each combination and get a result
$sum_price = 0;$items = [];$sum_energy = 0;
foreach($combo as $i => $o){
//loop through the array of true/false values determining if an item is on or off
if($o){
//if on, add item to result
$sum_price += $products[$i]['price'];
$sum_energy += $products[$i]['energy'];
$items[] = $products[$i];
}
}
if($sum_price <= $price_limit){
//if sum of result is within the price limit, add to the results array
$results[] = [
'items' => $items,
'price' => $sum_price,
'energy' => $sum_energy
];
}
}
$best = $results[0];$ra = [$best];
foreach($results as $k => $result){
if($k === 0){continue;}//skip first iteration as it was set above
//check if the energy is higher than the best, or if equal, check if the price is better
if($result['energy'] > $best['energy'] || ($result['energy'] === $best['energy'] && $result['price'] < $best['price'])){
//reset best to the current result, reset return array
$best = $result;
$ra = [$best];
}else if($result['energy'] === $best['energy']){
//current result is the same as best, add it to the return array
$ra[] = $result;
}
}
return $ra;
}
echo '<pre>'.json_encode(getBestProductCombinations($products,10),JSON_PRETTY_PRINT).' ';
Что тогда даст вам:
[
{
"items": [
{
"id": 3,
"price": 2.66,
"energy": 300
},
{
"id": 6,
"price": 7,
"energy": 1200
}
],
"price": 9.66,
"energy": 1500
}
]