寻找最佳组合的算法

http://en.wikipedia.org/wiki/Knapsack_problem

这个 背包问题 或 这是一个问题 combinatorial optimization :给定一组项目,每个项目都有一个重量和一个值,确定要包含在集合中的每个项目的数量,以便总重量小于或等于给定的限制,并且总值尽可能大。它的名字来源于某个被固定尺寸限制的人所面临的问题 knapsack 而且必须用最有价值的东西填满它。。。

linear programming 问题

确定实现最佳效果的方法 结果(如最大利润或 给定数学模型中的最低成本) 模型,并给出了一些 方程。

查看 Simplex Method .

您需要约束为0·includeItem的变量includeItem1,…,includeItemN 我 我 ,和includeItem1+…+includeItemN?15和includeItem1*价格项目1+。。。?10,最大化includeItem1*kilojouleItem1+。。。。

将其粘贴到您最喜欢的整数线性规划解算器中,并获得解决方案:)

另见 http://en.wikipedia.org/wiki/Linear_programming

说你的特定问题是NP完全问题是没有意义的,但它是NP完全问题的一个实例,所以可能没有问题 理论上

我不认为你的问题是ILP的一个特例,这使得它特别容易解决。把它看作一个类似背包的问题,你可以把自己限制在1..100的所有子集上,这些子集最多(或正好)有15个元素,这是n中的多项式——它是n-choose-15,小于(n^15)/(15!),但当n=100时,这并不是非常有用。

如果您想要为解算器程序提供建议,我已经尝试过glpk,并发现它使用起来很愉快。如果你想要花钱的东西,我的讲师总是以CPLEX为例。

这听起来很像背包问题。有多种方法(例如,按能量密度降序)。

这是背包问题,如果你可以选择一个产品或不。如果你可以选择乘积的分数,那么你可以用单纯形法来解决这个问题,但是分数背包问题有一个简单的解决方案。

按能量/价格比订购物品,从最高的物品中挑选100%直到你的钱用完,然后从剩余的最高物品中挑选一个零值。

例如,如果价格为4,3,5,4,能量为3,5,2,7,则订购为

所以你会选择第4项和第2项,花费7美元,剩下的3美元,你会以3美元的价格和3*.75=2.25的能量购买第一项的75%

请注意,与仅允许0%或100%相比,允许分数值将为您提供更高的目标值,因此没有任何整数解决方案优于14.25(或14,因为目标值必须是整数)。

1. 解决松弛问题,允许分数权重。如果该值小于z*,则放弃该分支。
3. 选择一个项目(比如列表中的第一个,最赚钱的项目)并形成两个子问题,其中一个是 必须 将其包含在解决方案中,然后 不能 将其包含在解决方案中(这是分支步骤)。
4. 只要您还有子问题要解决,选择一个并返回到步骤1。

请注意,当您创建子问题时,您必须选择一个项目,只需从预算中减去其价格并将其值添加到利润中,现在您有一个较小的问题要解决。

有关更详细的说明,请参阅 Branch and Bound

Stony Brook算法存储库列表 implementations for the knapsack problem.

他们的书 The Algorithm Design Manual 有关于大量问题的此类信息。

SELECT TOP 15 *
FROM Product
WHERE Price < 10
ORDER BY Energy DESC

这让我想起了著名的背包算法

http://en.wikipedia.org/wiki/Knapsack_problem

应该可以用计算机解决这个问题 Cream for Java . 还有一个C#版本可用 CSharpCream .

如果你想移植到c#,请随意。

x 最好的结果。

<?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).'</pre>';

这样你就可以:

[
    {
        "items": [
            {
                "id": 3,
                "price": 2.66,
                "energy": 300
            },
            {
                "id": 6,
                "price": 7,
                "energy": 1200
            }
        ],
        "price": 9.66,
        "energy": 1500
    }
]