Рассчитать, какие продукты вместе доставят запрошенную силу -- php поле с участием algorithm поле с участием optimization пол Связанный проблема

Calculate which products together would deliver the requested power


15
vote

проблема

русский

Допустим, у меня есть три продукта:

<Сильный> Продукт A Доставит 5 власти. Стоит 50.

Product B доставит 9 мощность. Стоит 80.

<Сильный> продукт C доставит 15 мощности. Стоит 140.

Я хочу знать, какую комбинацию продуктов я мог бы купить, когда мне нужно 7 власть. Я мог бы купить два <сильных> , но один из <сильный> b дешевле.

Когда мне нужна 65 власть. Мне потребуется 4 раза c и 1 раз (стоит 680). Но я также мог бы пойти на семь <сильных> б продуктов и один <сильный> (стоит 610).

Я ищу способ расчета возможных комбинаций продуктов для данного количества нужны мне.

То, как я пытался делать это, не дает мне, что я хочу:

 <код> // $products are sorted DESC on their $power $power = 65  while( $power > 0 ) {     foreach( $products as $productPower ) {         if( ( $productPower > $power && $power - $productPower > 0 ) || $productPower == end( $products ) ) {             // Add product to list             $power -= $productPower;             break;         }     }  }   

Этот пример код даст мне только 4 раза C и один раз <сильный> . Как мне идти?

<Сильные> Редактировать Количество продуктов - переменная. Кроме того, конкретная стоимость и мощность является переменной. Таким образом, могут быть 10 продуктов с более дорогими ценниками.

Редактировать 2 Как я уже сказал выше, я хочу рассчитать возможные <сильные> комбинации (множественное число). Некоторые люди, кажется, пропустили это в моем описании.

Английский оригинал

Let's say I've got three products:

Product A Will deliver 5 power. Costs 50.

Product B Will deliver 9 power. Costs 80.

Product C Will deliver 15 power. Costs 140.

I want to know what combination of products I could buy when I need 7 power. I could buy two of A but one of B is cheaper.

When I'd need 65 power. I would need 4 times C and 1 time A (costs 680). But I could also go for seven B products and one A (costs 610).

I am looking for a way to calculate the possible combinations of products for the given amount of power I need.

The way I tried doing this doesn't give me what I want:

// $products are sorted DESC on their $power $power = 65  while( $power > 0 ) {     foreach( $products as $productPower ) {         if( ( $productPower > $power && $power - $productPower > 0 ) || $productPower == end( $products ) ) {             // Add product to list             $power -= $productPower;             break;         }     }  } 

This sample code will only give me 4 times C and one time A. How should I go about it?

EDIT The number of products is variable. Also, the specific cost and power is variable. So there may be 10 products with cheeper and more expensive price tags.

EDIT 2 As I said above, I want to calculate the possible combinations (plural). Some people seem to have missed that in my description.

</div
        
         
         

Список ответов

5
 
vote

Обновлен ответ

Я стою с моим первоначальным ответом, но с тех пор вывел явное решение. К сожалению, я не разбираюсь в PHP, поэтому реализация, которую я представлю, это в (плохо написано) F #.

Точка, которая делает ваш вопрос интересным, заключается в том, что вы не ищете лучшее решение, но для всех возможных решений. Как я указал в своем первоначальном ответе, это сложно, потому что набор выполнимых решений бесконечно. В качестве иллюстрации, если вы хотите произвести 65 единиц, вы можете использовать 13xa, что дает мощность 5x13 = 65. Но затем, очевидно, любое решение, которое содержит более 13 единиц A, также будет решением.

Вы не можете вернуть бесконечный набор из функции. То, что вам нужно, это набор всех «граничных» случаев:

    .
  • Если решение содержит столько единиц как граничный чехол для всех продуктов, он действителен
  • Если блок может быть удален из граничного корпуса, и он все еще возможен, он больше невозможен.

, например, решение s = {a = 13; B = 0; C = 0} - граничный случай. Удалите одну единицу из любого продукта, и он не выполнен - ​​и если комбинация такова, что для каждого продукта он содержит больше единиц, чем S, это действительное решение, но «доминирующее» на S.

Другими словами, мы не можем вернуть все возможные решения, но мы можем вернуть «предел», который разделяет возможные и непрерывные решения.

Обратите внимание, что стоимость продукции не имеет значения здесь - после того, как у вас есть набор граничных случаев, вычисления стоимости решения тривиально.

Учитывая, что вы указываете, что количество продуктов может быть произвольным, это звучит как четкий случай для рекурсии.

Если у вас нет продукта, решение тривециально пустое - нет решения. Если у вас есть 1 продукт, решение потолка (цель / продукт. Если у вас есть 2 продукта, скажите A: 5 и B: 2, с целью 10, вы можете

    .
  • Использование 0 a - & gt; Остальная цель - 10, используйте 5 b (или более)
  • Использование 1 a - & gt; Оставшаяся цель 10 - 5, используйте 3 b (или более)
  • Использование 2 a - & gt; Оставшаяся цель 10 - 10, используйте 0 B (или более)

A Maxed Out, поэтому мы сделаем.

Обратите внимание, что я сортировал A и B, уменьшая мощность. Несоответствующий список тоже будет работать, но вы бы произвели «бесполезные» граничные точки. Например, мы получили бы [1 б; 2 а] и [2 b; 2 а].

Идея может быть распространена на полную рекурсию вдоль линий

 <код> ["A",1],["C",4]                 610 ["A",1],["B",5],["C",1]         590 ["A",4],["C",3]                 620 ["A",4],["B",5]                 600 ["A",7],["C",2]                 630 ["A",10],["C",1]                640 ["A",13]                        650 0  

Ниже представляет собой простую реализацию F #, которая может быть легко улучшена, и, надеюсь, передаду идею. Функция блоков возвращает минимальное количество единиц продукта с помощью значения мощности, необходимого для поставки целевой мощности, а рекурсивная функция решает создание комбинаций в список решений, кортежей с идентификатором продукта и количество единиц для использования: < / P >.

 <код> ["A",1],["C",4]                 610 ["A",1],["B",5],["C",1]         590 ["A",4],["C",3]                 620 ["A",4],["B",5]                 600 ["A",7],["C",2]                 630 ["A",10],["C",1]                640 ["A",13]                        650 1  

Я бы запустил это так:

 <код> ["A",1],["C",4]                 610 ["A",1],["B",5],["C",1]         590 ["A",4],["C",3]                 620 ["A",4],["B",5]                 600 ["A",7],["C",2]                 630 ["A",10],["C",1]                640 ["A",13]                        650 2  

Обратите внимание, что количество решений увеличится довольно быстро. Я провел ваш пример, который дал 28 решений. По мере увеличения количества продуктов и целевой мощности число граничных решений будет немного расширяться.

Я не могу кодировать в PHP вообще, но я предполагаю, что он поддерживает рекурсию - может быть, кто-то покажет рекурсивное решение в PHP? В любом случае, я надеюсь, что это поможет.

Интересный побочный вопрос будет насколько разные проблемы, если продукты могут быть приобретены в не целочисленных количествах. В этом случае граница действительно была бы поверхностью (многогранник, который я полагаю); Как описать это адекватно будет интересной проблемой!

<Сильный> Оригинальный ответ

Если я не понимаю, что ваш вопрос, То, что вы описываете, это то, что известно в оптимизации как AN Целочисленное линейное программирование , с хорошо установленным алгоритмы разрешения их. Ваша проблема звучит как изменение проблемы диеты (данные ингредиенты, найдите самый дешевый способ получить достаточно калорий для выживания), один из архетипов линейных программиров, с целочисленными переменными ограничениями.

Во-первых, решение вашей проблемы, как указано, имеет бесконечное количество решений; Предположим, что 5 X A - это решение вашей проблемы, то любая комбинация с более чем 5 единицами A также удовлетворит ваши требования.

Редактировать: Я понимаю, что я мог бы неправильно понять вашу проблему - я предположил, что вы можете купить любое количество каждого продукта. Если вы можете купить только 1 единицу каждого из каждого, это более легкая проблема: это все еще проблема программирования целочисленной, но проще одной, проблема Knaxackack.

Примечание. Кроме того, если вы можете не более целочисленные количества продуктов (не так, кажется, для вас), ваша проблема значительно легче решить.

Самый очевидный способ перезапустить вашу проблему, которая делает его стандартной проблемой оптимизации, которая может быть довольно легко решена:

Найти комбинацию n продуктов, которая имеет минимальную общую стоимость, подлежащая ограничению, что общая доставка энергии выше желаемого порога. (Я предполагаю, что общая стоимость, так и общая доставка энергии являются линейными функциями количества a, b, c ... куплены).

Я предполагаю, что это на самом деле то, что вы действительно хотите - лучшее решение вашей проблемы. Если вы действительно заинтересованы в перечислении всего решения, один из способов пойти, - идентифицировать границы, которые определяют возможности (то есть геометрическую границу, так что, если вы на одной стороне, вы знаете, это не решение, иначе это ). Это намного проще, если вы работаете с цифрами, которые не должны быть целыми числами.

Надеюсь, это поможет!

 

Updated answer

I stand with my original answer, but have since derived an explicit solution. Unfortunately, I am not versed in PHP, so the implementation I'll present is in (poorly written) F#.

The point which makes your question interesting is that you are not looking for THE best solution, but for all feasible solutions. As I pointed out in my original answer, this is tricky, because the set of feasible solutions is infinite. As an illustration, if you want to produce 65 units, you can use 13xA, which yields a power of 5x13 = 65. But then, obviously, any solution which contains more than 13 units of A will also be a solution.

You can't return an infinite set from a function. What you need here is the set of all "boundary" cases:

  • if a solution contains as many units as a boundary case for all products, it is valid
  • if a unit can be removed from a boundary case and it is still feasible, it is not feasible anymore.

For instance, the solution S = { A = 13; B = 0; C = 0 } is a boundary case. Remove one unit from any product, and it is not feasible - and if a combination is such that for every product, it contains more units than S, it is a valid solution, but "dominated" by S.

In other words, we cannot return all possible solutions, but we can return the "limit" that separates feasible and unfeasible solutions.

Note also that the cost of the Products is irrelevant here - once you have the set of boundary cases, computing the cost of a solution is trivial.

Given that you specify that the number of products could be arbitrary, this sounds like a clear case for recursion.

If you have no product, the solution is trivially empty - there is no solution. If you have 1 product, the solution is ceiling (target / product.Power) If you have 2 products, say A:5 and B:2, with a target of 10, you could

  • use 0 of A -> remaining target is 10, use 5 B (or more)
  • use 1 of A -> remaining target is 10 - 5, use 3 B (or more)
  • use 2 of A -> remaining target is 10 - 10, use 0 B (or more)

A is maxed out, so we are done.

Note that I sorted A and B by decreasing Power. An unsorted list would work, too, but you would produced "useless" boundary points. For instance, we would get [1 B; 2 A], and [2 B; 2 A].

The idea can be extended to a full recursion, along the lines of

Given a list of Products and a remaining Target power to achieve, If the Product is the last one in the list, use ceiling of Target/product Power, Else take every possible combination of the head product from 0 to max, and Search deeper, decreasing Target Power by the units supplied by the Product selected. 

Below is a simple F# implementation, which could easily be improved upon, and will hopefully convey the idea. The units function returns the minimum number of units of a product with Power value required to supply target Power, and the recursive function solve builds up the combinations into a List of solutions, tuples with a Product Id and the number of units to use:

type Product = { Id: string; Power: int } let A = { Id = "A"; Power = 5 } let B = { Id = "B"; Power = 9 } let C = { Id = "C"; Power = 15 }  let products = [ A; B; C ] |> List.sortBy(fun e -> - e.Power)  let units (target: int) (value: int) =     if target < 0     then 0     else         (float)target / (float)value |> ceil |> (int)  let rec solve (products: Product list)                (current: (string * int) list)                (solutions: (string * int) list list)                (target: int) =     match products with     | [ ] -> [ ]     | [ one ] -> ((one.Id, (units target one.Power)) :: current) :: solutions     | hd :: tl ->         let max = units target hd.Power         [ 0 .. max ]         |> List.fold (fun s u ->             solve tl ((hd.Id, u) :: current) s (target - u * hd.Power)) solutions 

I would run it this way:

> solve [B;A] [] [] 65;; Real: 00:00:00.001, CPU: 00:00:00.000, GC gen0: 0, gen1: 0, gen2: 0 val it : (string * int) list list =   [[("A", 0); ("B", 8)]; [("A", 1); ("B", 7)]; [("A", 3); ("B", 6)];    [("A", 4); ("B", 5)]; [("A", 6); ("B", 4)]; [("A", 8); ("B", 3)];    [("A", 10); ("B", 2)]; [("A", 12); ("B", 1)]; [("A", 13); ("B", 0)]] 

Note that the number of solutions will increase pretty fast. I ran your example, which yielded 28 solutions. As the number of products and the target power increases, the number of boundary solutions will expand quite a bit.

I can't code in PHP at all, but I assume it supports recursion - maybe someone will show a recursive solution in PHP? In any case, I hope this helps.

An interesting side question would be how different the problem would be, if the products could be purchased in non-integer quantities. In that case, the boundary would really be a surface (a polyhedron I believe); how to describe it adequately would be an interesting problem!

Original answer

Unless I am misunderstanding your question, what you describe is what is known in optimization as an Integer Linear Programming problem, with well established algorithms to resolve them. Your problem sounds like a variation of the Diet problem (given ingredients, find the cheapest way to get enough calories to survive), one of the archetypes of Linear Programming, with integer variable constraints.

First, the solution to your problem as stated has an infinite numbers of solutions; suppose that 5 x A is a solution to your problem, then any combination with more than 5 units of A will also satisfy your requirements.

Edit: I realize I might have misunderstood your problem - I assumed you could buy any quantity of each product. If you can buy only 1 unit of each, this is an easier problem: it is still an integer programming problem, but a simpler one, the Knapsack problem.

Note also that if you can by non-integer quantities of the products (doesn't seem to be the case for you), your problem is significantly easier to solve.

The most obvious way to restate your problem, which make it a standard optimization problem that can be solved fairly easily:

Find the combination of n Products which has the minimum total cost, subject to constraint that the total energy delivered is above desired threshold. (I assume that both the total cost and total energy delivered are linear functions of the quantity of A, B, C... purchased).

I assume this is actually what you really want - the best possible solution to your problem. If you are really interested in enumerating all the solution, one way to go about it is to identify the boundaries which define the feasible set (i.e. the geometric boundary such that if you are on one side you know it's not a solution, otherwise it is). This is much easier if you are working with numbers that don't have to be integers.

Hope this helps!

</div
 
 
 
 
9
 
vote
vote
Лучший ответ
 

Введение

Это было бы a Проблема knaxack но, потому что вы не просто ищете Оптимальное решение вы также хотите найти всю возможную комбинацию

Тогда вы можете решить эту работу Проблема подмножества Сумма + изменение монет , чтобы получить:

    .
  • Перечислите все возможные комбинации и не просто общая комбинация
  • Получить лучшую комбинацию

    например, для n = 4, s = {1,2,3}, есть четыре решения: {1,1,1,1}, {1,1,2} , {2,2}, {1,3}.

Пример 1

 <код> echo "<pre>"; $start = microtime(true);  // Start Finder $finder = new CombinationFinder(65);  // Add Produts $finder->addProduct(new Product("A", 5, 50)); $finder->addProduct(new Product("B", 9, 80)); $finder->addProduct(new Product("C", 15, 140));  // Output All Found Combinations foreach ( $finder as $key => $sales ) {     echo $sales->getName(), "   ", $sales->getCombinationCost(), PHP_EOL; }  // Get Best Combination echo "Combination: ", $finder->getBestCombination()->getName(), PHP_EOL; echo "Cost: ", number_format($finder->getBestCombination()->getCombinationCost(), 2), PHP_EOL;  // Total Time echo PHP_EOL, microtime(true) - $start;   

Выход

Лучшие комбинации

 <код> ["A",1],["C",4]                 610 ["A",1],["B",5],["C",1]         590 ["A",4],["C",3]                 620 ["A",4],["B",5]                 600 ["A",7],["C",2]                 630 ["A",10],["C",1]                640 ["A",13]                        650   

Лучшая комбинация

 <код> Combination: ["A",1],["B",5],["C",1] Cost: 590.00   

Общее время

 <код> 0.2533269405365   

Лучшая комбинация

Вы можете увидеть лучшую комбинацию <код> A*1 ,B*5 ,C*1 .. сломается

 <код>             A          B           C Power : 5   *  1 +  9  *  5 +  15  *  1    =   65 Cost  : 50  *  1 +  80 *  5 +  140 *  1    =   590   <---- Better than 610.00      

Пример 2

Класс может быть использован для 2, 3, 4 или более комбинации продукта, и все же подоконник очень быстро

 <код> echo "<pre>"; $start = microtime(true);  // Start Finder $finder = new CombinationFinder(65);  // Add Produts $finder->addProduct(new Product("A", 5, 50)); $finder->addProduct(new Product("B", 9, 80)); $finder->addProduct(new Product("C", 15, 140)); $finder->addProduct(new Product("D", 20, 120)); // more product class  $finder->run(); // just run  // Get Best Combination echo "Combination: ", $finder->getBestCombination()->getName(), PHP_EOL; echo "Cost: ", number_format($finder->getBestCombination()->getCombinationCost(), 2), PHP_EOL;  // Total Time echo PHP_EOL, microtime(true) - $start;   

<Сильные> Выход

 <код> Combination: ["A",1],["D",3]    //<---------------------- Best Combination Cost: 410.00   

<Сильное> Время принято

 <код> 1.1627659797668  // less than 2 sec    

Используемый класс

 <код> class Product {     public $name;     public $power;     public $cost;     public $unit;      function __construct($name, $power, $cost) {         $this->name = $name;         $this->power = $power;         $this->cost = $cost;         $this->unit = floor($cost / $power);     } }    class Sales {     /**      *      * @var Product      */     public $product;     public $count;     public $salePower;     public $saleCost;      function __construct(Product $product, $count) {         $this->product = $product;         $this->count = $count;         $this->salePower = $product->power * $count;         $this->saleCost = $product->cost * $count;     } }    class SalesCombination {     private $combinationPower;     private $combinationCost;     private $combinationName;     private $combinationItems;     private $args;      function __construct(array $args) {         list($this->combinationPower, $this->combinationCost, $this->combinationItems) = array_reduce($args, function ($a, $b) {             $a[0] += $b->salePower;             $a[1] += $b->saleCost;             $a[2] = array_merge($a[2], array_fill(0, $b->count, $b->product->name));             return $a;         }, array(0,0,array()));         $this->args = $args;     }      function getName() {         $values = array_count_values($this->combinationItems);         $final = array();         foreach ( $values as $name => $amount ) {             $final[] = array($name,$amount);         }         return substr(json_encode($final), 1, -1);     }      function getCombinationPower() {         return $this->combinationPower;     }      function getCombinationCost() {         return $this->combinationCost;     } }     class CombinationFinder implements IteratorAggregate, Countable {     private $sales;     private $products = array();     private $power;     private $found = array();     private $bestCombination = null;     private $run = false;      function __construct($power) {         $this->power = $power;     }      function addProduct(Product $product) {         $this->products[] = $product;     }      function getBestCombination() {         return $this->bestCombination;     }      function getFound() {         return $this->found ?  : array();     }      public function getIterator() {         if ($this->run === false) {             $this->run();         }         return new ArrayIterator($this->found);     }      public function count() {         return count($this->found);     }      function run() {         $this->run = true;         $this->buildSales();         $u = new UniqueCombination($this->sales);         $u->setCallback(array($this,"find"));         $u->expand();     }      function find() {         $salesCombination = new SalesCombination(func_get_args());         if ($salesCombination->getCombinationPower() == $this->power) {             isset($this->bestCombination) or $this->bestCombination = $salesCombination;             $salesCombination->getCombinationCost() < $this->bestCombination->getCombinationCost() and $this->bestCombination = $salesCombination;             $this->found[sha1($salesCombination->getName())] = $salesCombination;         }     }      function buildSales() {         $total = count($this->products);         foreach ( $this->products as $product ) {             $max = floor($this->power / $product->power);             for($i = 1; $i <= $max; $i ++) {                 $this->sales[$product->name][] = new Sales($product, $i);             }         }     } }  class UniqueCombination {     private $items;     private $result = array();     private $callback = null;      function __construct($items) {         $this->items = array_values($items);     }      function getResult() {         return $this->result;     }      function setCallback($callback) {         $this->callback = $callback;     }      function expand($set = array(), $index = 0) {         if ($index == count($this->items)) {             if (! empty($set)) {                 $this->result[] = $set;                 if (is_callable($this->callback)) {                     call_user_func_array($this->callback, $set);                 }             }             return;         }         $this->expand($set, $index + 1);         foreach ( $this->items[$index] as $item ) {             $this->expand(array_merge($set, array($item)), $index + 1);         }     } }   
 

Introduction

This would have been a Knapsack problem but because you are not not just looking for the optimal solution you also want to find all possible combination

Then you can solve this Subset sum problem + Coin Change to get :

  • List all possible Combination and not just total combination
  • Get Best Combination

    For example, for N = 4,S = {1,2,3}, there are four solutions: {1,1,1,1},{1,1,2},{2,2},{1,3}.

Example 1

echo "<pre>"; $start = microtime(true);  // Start Finder $finder = new CombinationFinder(65);  // Add Produts $finder->addProduct(new Product("A", 5, 50)); $finder->addProduct(new Product("B", 9, 80)); $finder->addProduct(new Product("C", 15, 140));  // Output All Found Combinations foreach ( $finder as $key => $sales ) {     echo $sales->getName(), "   ", $sales->getCombinationCost(), PHP_EOL; }  // Get Best Combination echo "Combination: ", $finder->getBestCombination()->getName(), PHP_EOL; echo "Cost: ", number_format($finder->getBestCombination()->getCombinationCost(), 2), PHP_EOL;  // Total Time echo PHP_EOL, microtime(true) - $start; 

Output

Top Combinations

["A",1],["C",4]                 610 ["A",1],["B",5],["C",1]         590 ["A",4],["C",3]                 620 ["A",4],["B",5]                 600 ["A",7],["C",2]                 630 ["A",10],["C",1]                640 ["A",13]                        650 

Best Combination

Combination: ["A",1],["B",5],["C",1] Cost: 590.00 

Total Time

0.2533269405365 

Best Combination

You can see the best Combination is A*1 ,B*5 ,C*1 .. Break down

            A          B           C Power : 5   *  1 +  9  *  5 +  15  *  1    =   65 Cost  : 50  *  1 +  80 *  5 +  140 *  1    =   590   <---- Better than 610.00    

Example 2

The class can be use for 2, 3 , 4 or more product combination and yet sill very fast

echo "<pre>"; $start = microtime(true);  // Start Finder $finder = new CombinationFinder(65);  // Add Produts $finder->addProduct(new Product("A", 5, 50)); $finder->addProduct(new Product("B", 9, 80)); $finder->addProduct(new Product("C", 15, 140)); $finder->addProduct(new Product("D", 20, 120)); // more product class  $finder->run(); // just run  // Get Best Combination echo "Combination: ", $finder->getBestCombination()->getName(), PHP_EOL; echo "Cost: ", number_format($finder->getBestCombination()->getCombinationCost(), 2), PHP_EOL;  // Total Time echo PHP_EOL, microtime(true) - $start; 

Output

Combination: ["A",1],["D",3]    //<---------------------- Best Combination Cost: 410.00 

Time Taken

1.1627659797668  // less than 2 sec  

Class Used

class Product {     public $name;     public $power;     public $cost;     public $unit;      function __construct($name, $power, $cost) {         $this->name = $name;         $this->power = $power;         $this->cost = $cost;         $this->unit = floor($cost / $power);     } }    class Sales {     /**      *      * @var Product      */     public $product;     public $count;     public $salePower;     public $saleCost;      function __construct(Product $product, $count) {         $this->product = $product;         $this->count = $count;         $this->salePower = $product->power * $count;         $this->saleCost = $product->cost * $count;     } }    class SalesCombination {     private $combinationPower;     private $combinationCost;     private $combinationName;     private $combinationItems;     private $args;      function __construct(array $args) {         list($this->combinationPower, $this->combinationCost, $this->combinationItems) = array_reduce($args, function ($a, $b) {             $a[0] += $b->salePower;             $a[1] += $b->saleCost;             $a[2] = array_merge($a[2], array_fill(0, $b->count, $b->product->name));             return $a;         }, array(0,0,array()));         $this->args = $args;     }      function getName() {         $values = array_count_values($this->combinationItems);         $final = array();         foreach ( $values as $name => $amount ) {             $final[] = array($name,$amount);         }         return substr(json_encode($final), 1, -1);     }      function getCombinationPower() {         return $this->combinationPower;     }      function getCombinationCost() {         return $this->combinationCost;     } }     class CombinationFinder implements IteratorAggregate, Countable {     private $sales;     private $products = array();     private $power;     private $found = array();     private $bestCombination = null;     private $run = false;      function __construct($power) {         $this->power = $power;     }      function addProduct(Product $product) {         $this->products[] = $product;     }      function getBestCombination() {         return $this->bestCombination;     }      function getFound() {         return $this->found ?  : array();     }      public function getIterator() {         if ($this->run === false) {             $this->run();         }         return new ArrayIterator($this->found);     }      public function count() {         return count($this->found);     }      function run() {         $this->run = true;         $this->buildSales();         $u = new UniqueCombination($this->sales);         $u->setCallback(array($this,"find"));         $u->expand();     }      function find() {         $salesCombination = new SalesCombination(func_get_args());         if ($salesCombination->getCombinationPower() == $this->power) {             isset($this->bestCombination) or $this->bestCombination = $salesCombination;             $salesCombination->getCombinationCost() < $this->bestCombination->getCombinationCost() and $this->bestCombination = $salesCombination;             $this->found[sha1($salesCombination->getName())] = $salesCombination;         }     }      function buildSales() {         $total = count($this->products);         foreach ( $this->products as $product ) {             $max = floor($this->power / $product->power);             for($i = 1; $i <= $max; $i ++) {                 $this->sales[$product->name][] = new Sales($product, $i);             }         }     } }  class UniqueCombination {     private $items;     private $result = array();     private $callback = null;      function __construct($items) {         $this->items = array_values($items);     }      function getResult() {         return $this->result;     }      function setCallback($callback) {         $this->callback = $callback;     }      function expand($set = array(), $index = 0) {         if ($index == count($this->items)) {             if (! empty($set)) {                 $this->result[] = $set;                 if (is_callable($this->callback)) {                     call_user_func_array($this->callback, $set);                 }             }             return;         }         $this->expand($set, $index + 1);         foreach ( $this->items[$index] as $item ) {             $this->expand(array_merge($set, array($item)), $index + 1);         }     } } 
</div
 
 
 
 
4
 
vote

Простое наблюдение по этой конкретной проблеме может помочь людям в решении этого вопроса. Способ питания и расходы распределяются здесь. Вы получаете наибольшее значение для ваших денег с продуктом B. На самом деле, единственное время, когда вы когда-либо будете использовать продукт C, является когда вам нужна ровно 15 мощность или 28-30 мощности.

Так что для любой силы, необходимой выше 30, просто используйте целочисленное разделение, чтобы получить нужную # продукта B:

 <код> ["A",1],["C",4]                 610 ["A",1],["B",5],["C",1]         590 ["A",4],["C",3]                 620 ["A",4],["B",5]                 600 ["A",7],["C",2]                 630 ["A",10],["C",1]                640 ["A",13]                        650 3  

Тогда узнайте, насколько вам нужна энергия:

 <код> ["A",1],["C",4]                 610 ["A",1],["B",5],["C",1]         590 ["A",4],["C",3]                 620 ["A",4],["B",5]                 600 ["A",7],["C",2]                 630 ["A",10],["C",1]                640 ["A",13]                        650 4  

Если остаток превышает 5, просто добавьте еще один продукт B, а также использовать 1 продукт A:

 <код> ["A",1],["C",4]                 610 ["A",1],["B",5],["C",1]         590 ["A",4],["C",3]                 620 ["A",4],["B",5]                 600 ["A",7],["C",2]                 630 ["A",10],["C",1]                640 ["A",13]                        650 5  

Полная функция будет выглядеть что-то подобное:

 <код> ["A",1],["C",4]                 610 ["A",1],["B",5],["C",1]         590 ["A",4],["C",3]                 620 ["A",4],["B",5]                 600 ["A",7],["C",2]                 630 ["A",10],["C",1]                640 ["A",13]                        650 6  
 

A simple observation on this specific problem may help people in solving this question. The way the power and costs are distributed here. You get the most value for your money with Product B. In fact, the only time you would ever use Product C, is when you need exactly 15 power, or 28-30 power.

So for any power needed above 30, just use integer division to get the # of Product B's you need by:

int num_productB = power_needed/9; 

Then find out how much more power you need by:

int leftover = power_needed % 9; 

If the leftover is greater than 5, just add one more Product B, Else use 1 Product A:

if(leftover > 5)      num_productB++; else      productA = 1; 

The full function would look something like this:

function computeBestCombination($power_needed){ $power_results = array(); //index 0 = Product A //index 1 = Product B //index 2 = Product C if($power_needed == 15){     $power_results[0] = 0;     $power_results[1] = 0;     $power_results[2] = 1; } else if($power_needed >= 28 && $power_needed <= 30)     $power_results[0] = 0;     $power_results[1] = 0;     $power_results[2] = 2; else{     $power_results[1] = $power_needed / 9;     $left_over = $power_needed % 9;     if($left_over > 5){         $power_results[1]++;     }     else{         $power_results[0] = 1;     }     $power_results[2] = 0; } return $power_results; } 
</div
 
 
 
 
1
 
vote

Проверьте этот код:

 <код> ["A",1],["C",4]                 610 ["A",1],["B",5],["C",1]         590 ["A",4],["C",3]                 620 ["A",4],["B",5]                 600 ["A",7],["C",2]                 630 ["A",10],["C",1]                640 ["A",13]                        650 7  

Это будет печать:

массив ( [0] = & gt; 9. [1] = & gt; 9. [2] = & gt; 9. [3] = & gt; 9. [4] = & gt; 9. [5] = & gt; 9. [6] = & gt; 9. [7] = & gt; 5. )

Что является правильным решением.

p.d: Конечно, вы можете оптимизировать функцию.

 

Check this code:

<?php $products = array(5 => 50, 9 => 80, 15 => 140);  $power = 65; $output = array();  function calculate_best_relation($products, $power, &$output) {   $aux = array_keys($products);   sort($aux);    $min = $aux[0];   if ($power <= $min) {     $output[] = $min;     return $output;   }   else {     //Calculate best relation     $relations = array();     foreach ($products as $p => $c) {       $relations[$p] = $c / $p;     }     asort($relations);      foreach($relations as $p => $c) {       if ($power > $c) {         $output[] = $p;         $power -= $c;         calculate_best_relation($products, $power, $output);         break;       }     }   } }  calculate_best_relation($products, $power, $output);  print_r($output); ?> 

This will print:

Array ( [0] => 9 [1] => 9 [2] => 9 [3] => 9 [4] => 9 [5] => 9 [6] => 9 [7] => 5 )

Which is the correct solution.

P.D: Surely you can optimize the function.

</div
 
 
 
 
1
 
vote

Целочисленный пакет программирования, такой как пульпа, сделает это просто, как пирог.

Вот красивая Пример , который будет руководить вами через процесс. < / P >.

Установите Python, а затем Easy_install Pulp, и это будет работать.

Код должен быть легко читать и следовать тоже.

 <код> ["A",1],["C",4]                 610 ["A",1],["B",5],["C",1]         590 ["A",4],["C",3]                 620 ["A",4],["B",5]                 600 ["A",7],["C",2]                 630 ["A",10],["C",1]                640 ["A",13]                        650 8  

Больше продуктов:

 <код> ["A",1],["C",4]                 610 ["A",1],["B",5],["C",1]         590 ["A",4],["C",3]                 620 ["A",4],["B",5]                 600 ["A",7],["C",2]                 630 ["A",10],["C",1]                640 ["A",13]                        650 9  

 

An integer programming package such as pulp will make this easy as pie.

Here is a beautiful example that will guide you through the process.

Install python and then easy_install pulp and this will work.

The code should be easy to read and follow too.

__author__ = 'Robert' import pulp  def get_lp_problem(products, required_power):     prob = pulp.LpProblem("MyProblem", pulp.LpMinimize)     total_cost = []     total_power = []     for product in products:         var = pulp.LpVariable(product.name,             lowBound=0,             upBound=None,             cat=pulp.LpInteger)         total_cost.append(var * product.cost)         total_power.append(var * product.power)      prob += sum(total_power) >= required_power #ensure we have required power     prob += sum(total_cost) #minimize total cost!     return prob  def solve(products, required_power):     lp_prob = get_lp_problem(products, required_power)     lp_prob.solve()     print lp_prob.solutionTime #0.01 seconds     for var in lp_prob.variables():         print var.name, var.varValue   from collections import namedtuple Product = namedtuple("Product", "name, power, cost") products = [     Product('A', 5, 50),     Product('B', 9, 80),     Product('C', 15, 140) ] solve(products, 7) """ A 0.0 B 1.0 C 0.0  cost = 0*50 + 1*80 + 0*140 = 80 power = 0*5 + 1*9 + 0*15 = 9 """  solve(products, 65) """ A 1.0 B 5.0 C 1.0  cost = 1*50 + 5*80 + 1*140 = 590 power = 1*5 + 5*9 + 1*15 = 65 """ 

more products:

products = [Product(i, i, i-i/100) for i in range(1000)] solve(products, 12345) """ solution time: 0.0922736688601 1 45.0 100 123.0 power = 123*100 + 45*1 =12345   """ 
</div
 
 
 
 
1
 
vote

Это довольно красиво решается с помощью Динамическое программирование . Хитрость заключается в нахождении математической связи между все более большим значениями и предыдущими, меньшими значениями.

Так что позвольте <код> C(p) быть стоимостью для мощности P . Тогда мы знаем следующее из ваших базовых случаев:

Допустим, у меня есть три продукта:

Продукт A доставит 5 мощность. Стоит 50.

Продукт B доставит 9 мощности. Стоит 80.

Продукт C будет доставить 15 мощности. Стоит 140.

 <код> C(5) = 50 C(9) = 80 C(15) = 140   

Вы можете определить базовые случаи, однако вы хотите. Предположительно <код> C(0) = 0 , но это не дано.

Тогда трюк - найти рекурсию, чтобы решить это. Используя заданные значения, мы получаем

 <код> C(p) = Min(C(p-5) + 50, C(p-9) + 80, C(p-15) + 140)   

В целом, вы должны повторять каждый из базовых случаев и посмотреть, какой путь дешевле.

Теперь вы остались двумя способами создания вашего решения: рекурсивно или используя динамическое программирование. Первый легче учитываться рекурсивной функцией, но, очевидно, довольно неэффективна. Другой способ сделать это, то должен начать внизу и создать свое решение итеративно.

Позвольте сказать, что вы хотите найти стоимость Power Power. Тогда следующий псевдокод будет работать:

 <код> // Create an array big enough to hold elements 0 through p inclusive. var solution = new Array(p+1);  // Initialize the array with the base cases. for each base case b:   solution[power(b)] = cost(b);  // Now we build the array moving forward for i from 0 to p:   // Start with a really big number   solution[i] = +Infinity;    // Iterate over base case to see what the cheapest way to get i power is.   for each base case b:     solution[i] = min(solution[i], solution[i - power(b)] + cost(b);  // The final answer is the last element in the array, but you get everything // else for free. You can even work backwards and figure out the cheapest // combination! return solution[p]   

Анализ оставлен как упражнение для читателя: -)

 

This is pretty nicely solved using dynamic programming. The trick is in finding the mathematical relationship between increasingly large values and previous, smaller values.

So let C(p) be the cost for p power. Then we know the following from your base cases:

Let's say I've got three products:

Product A Will deliver 5 power. Costs 50.

Product B Will deliver 9 power. Costs 80.

Product C Will deliver 15 power. Costs 140.

C(5) = 50 C(9) = 80 C(15) = 140 

You can define the base cases however you want. Presumably C(0) = 0, but that is not given.

Then the trick is to find the recursion to solve this. Using the given values, we get

C(p) = Min(C(p-5) + 50, C(p-9) + 80, C(p-15) + 140) 

More generally, you have to iterate over each of the base cases and see which way is cheaper.

So now you're left with two ways to build your solution: recursively or using dynamic programming. The former is easier given the recursive function, but is obviously quite inefficient. The other way to do this, then, is to start at the bottom and build your solution iteratively.

Lets say you want to find the cost for p power. Then the following pseudocode will work:

// Create an array big enough to hold elements 0 through p inclusive. var solution = new Array(p+1);  // Initialize the array with the base cases. for each base case b:   solution[power(b)] = cost(b);  // Now we build the array moving forward for i from 0 to p:   // Start with a really big number   solution[i] = +Infinity;    // Iterate over base case to see what the cheapest way to get i power is.   for each base case b:     solution[i] = min(solution[i], solution[i - power(b)] + cost(b);  // The final answer is the last element in the array, but you get everything // else for free. You can even work backwards and figure out the cheapest // combination! return solution[p] 

Analysis left as an exercise to the reader :-)

</div
 
 
0
 
vote

Вы хотите оптимизировать следующую функцию

 <код> $cost = $amountOfProductA * $costOfProductA + $amountOfProductB * $costOfProductB + $amountOfProductC * $costOfProductC   

со следующим ограничением

 <код> $powerDeliveredByA * $amountOfProductA + $powerDeliveredByB * $amountOfProductB + $powerDeliveredByC * $amountOfProductC = 65   

Итак, эти линии находят решения, которые выходят 65 (или близко к 65, используя приемлемый порог, который вы должны настроить), затем сортировать массив решений по стоимости и получить первый элемент массива решений:

.
 <код> $requiredPower = 65; $productA = array('amount' => 0, 'cost' => 50, 'powerDelivered' => 5); $productB = array('amount' => 0, 'cost' => 80, 'powerDelivered' => 9); $productC = array('amount' => 0, 'cost' => 140, 'powerDelivered' => 15); $increment = 0.01; $threshold = 0.01; $solutions = array(); while($productA['amount'] * $productA['powerDelivered'] < $requiredPower) {     $productC['amount'] = 0;     while($productB['amount'] * $productB['powerDelivered'] < $requiredPower)     {         $productC['amount'] = 0;         while($productC['amount'] * $productC['powerDelivered'] < $requiredPower)         {             if($productA['amount'] * $productA['powerDelivered'] + $productB['amount'] * $productB['powerDelivered'] + $productC['amount'] * $productC['powerDelivered'] > $requiredPower + $threshold)             {                 break;             }             if(isWithinThreshold($productA['powerDelivered'] * $productA['amount'] + $productB['powerDelivered'] * $productB['amount'] + $productC['powerDelivered'] * $productC['amount'], $requiredPower, $threshold))             {                 //var_dump($productA['powerDelivered'] * $productA['amount'] + $productB['powerDelivered'] * $productB['amount'] + $productC['powerDelivered'] * $productC['amount']);                 $cost = $productA['amount'] * $productA['cost'] + $productB['amount'] * $productB['cost'] + $productC['amount'] * $productC['cost'];                 $solutions[number_format($cost,10,'.','')] = array('cost' => $cost, 'qA' => $productA['amount'], 'qB' => $productB['amount'], 'qC' => $productC['amount']);             }             $productC['amount'] = $productC['amount'] + $increment;         }         $productB['amount'] = $productB['amount'] + $increment;     }     $productA['amount'] = $productA['amount'] + $increment; } ksort($solutions, SORT_NUMERIC); $minimumCost = array_shift($solutions); var_dump($minimumCost);  //checks if $value1 is within $value2 +- $threshold function isWithinThreshold($value1, $value2, $threshold) {     if($value1 >= $value2 - $threshold && $value1 <= $value2 + $threshold)     {         return true;     } }   

Способ оптимизации функции описан здесь: Оптимизация функций

 

You want to optimize the following function

$cost = $amountOfProductA * $costOfProductA + $amountOfProductB * $costOfProductB + $amountOfProductC * $costOfProductC 

With the following restriction

$powerDeliveredByA * $amountOfProductA + $powerDeliveredByB * $amountOfProductB + $powerDeliveredByC * $amountOfProductC = 65 

So these lines find solutions that yield 65 (or close to 65, using an acceptable threshold you'd have to set), then sort the solutions array by the cost, and get the first element of the solutions array:

$requiredPower = 65; $productA = array('amount' => 0, 'cost' => 50, 'powerDelivered' => 5); $productB = array('amount' => 0, 'cost' => 80, 'powerDelivered' => 9); $productC = array('amount' => 0, 'cost' => 140, 'powerDelivered' => 15); $increment = 0.01; $threshold = 0.01; $solutions = array(); while($productA['amount'] * $productA['powerDelivered'] < $requiredPower) {     $productC['amount'] = 0;     while($productB['amount'] * $productB['powerDelivered'] < $requiredPower)     {         $productC['amount'] = 0;         while($productC['amount'] * $productC['powerDelivered'] < $requiredPower)         {             if($productA['amount'] * $productA['powerDelivered'] + $productB['amount'] * $productB['powerDelivered'] + $productC['amount'] * $productC['powerDelivered'] > $requiredPower + $threshold)             {                 break;             }             if(isWithinThreshold($productA['powerDelivered'] * $productA['amount'] + $productB['powerDelivered'] * $productB['amount'] + $productC['powerDelivered'] * $productC['amount'], $requiredPower, $threshold))             {                 //var_dump($productA['powerDelivered'] * $productA['amount'] + $productB['powerDelivered'] * $productB['amount'] + $productC['powerDelivered'] * $productC['amount']);                 $cost = $productA['amount'] * $productA['cost'] + $productB['amount'] * $productB['cost'] + $productC['amount'] * $productC['cost'];                 $solutions[number_format($cost,10,'.','')] = array('cost' => $cost, 'qA' => $productA['amount'], 'qB' => $productB['amount'], 'qC' => $productC['amount']);             }             $productC['amount'] = $productC['amount'] + $increment;         }         $productB['amount'] = $productB['amount'] + $increment;     }     $productA['amount'] = $productA['amount'] + $increment; } ksort($solutions, SORT_NUMERIC); $minimumCost = array_shift($solutions); var_dump($minimumCost);  //checks if $value1 is within $value2 +- $threshold function isWithinThreshold($value1, $value2, $threshold) {     if($value1 >= $value2 - $threshold && $value1 <= $value2 + $threshold)     {         return true;     } } 

The way to optimize a function is described here: Function Optimization

</div
 
 
         
         

Связанный проблема

1  Как использовать URLFetch в PHP  ( How to use urlfetch in php ) 
Где я могу получить файлы библиотеки API или PHP для использования URLFetch? Я искал в нескольких местах в документации по двигателю Google App. Мне удалось...

1  Экспорт Результат MySQL для Excel  ( Export mysql result to excel ) 
Я нашел небольшой скрипт, который будет экспортировать информацию в файл XLS, но я не могу, кажется, не могу работать. Оригинальный код найден здесь: http: /...

19  Как я могу получить простоту PHP (развертывание), но мощность Perl?  ( How can i get phps deployment simplicity but perls power ) 
Я презираю язык PHP, и я совершенно уверен, что я не одинок. Но великая вещь о PHP - это способ, которым mod_php принимает и скрывает детали образования горы ...

21  Нарезка многомерного массива PHP через один из его элементов  ( Slicing a multi dimensional php array across one of its elements ) 
сказать, например, вы только что запрашивали базу данных, и вы получили этот 2D-массив. <код> $results = array( array('id' => 1, 'name' => 'red' , 'spi...

1  Запрос CURL PHP для ошибки возврата веб-службы  ( Php curl request for web service returning error ) 
Я продолжаю получать ошибку: «Не удалось отменить сущность Serialize» при выполнении запроса на отдых ниже. Я предполагаю, что это связано с форматированием м...

0  Если запись в таблице A не существует в таблице b сделать что-то, как бы я пошел по этому поводу?  ( If record in table a does not exist in table b do something how would i go abou ) 
У меня есть таблица A с полем, называемым писем, мне нужно проверить таблицу B, которая также имеет поле под названием Emails. Если электронное письмо в табли...

6  CloudFlare API Перевести зависть в PHP Curl и отправить обновление CNAME  ( Cloudflare api translate curl to php curl and send cname update ) 
Это вопрос и ответ после многих исследований, используя некоторую информацию из других ответов, обнаруженных на StackoverFlow. Как конвертировать command-li...

2  Как загрузить OpenSSL.SO Динамическая библиотека в PHP 5.2.1  ( How to load openssl so dynamic library in php 5 2 1 ) 
Я недавно установил MAMP версию 1.6 на моем Mac OS 10.5.7. Теперь я управляю сценарием для подключения к сайту с помощью SSL. После некоторых исследований я...

0  Создание электронной почты на основе запроса MySQL  ( Generating an email based on mysql query ) 
У меня есть 2 таблицы, отображаемые ниже. Похожие словари: . + -------------------------------- + |. Пользователь |. ilike |. + ---------------------------...

1  PHP UNIX Время отсутствует Zeros  ( Php unix time missing zeros ) 
Хорошо, поэтому у меня есть следующая формула, но по какой-то причине, когда я не могу сказать, если это 5 минут или 50 минут, потому что он либо не отображае...

0  Как я могу получить значение группы записей в группу столбца, используя с функцией в Laravel Eloquent ORM  ( How can i get count of records group by a column using with function in laravel ) 
Мне нужно получить количество записей <код> groupBy с использованием <код> with() функция, известная как adgerage loading. У меня есть две таблицы, имеющие ...

1  Почему PHP не может создать файл, даже с 777 разрешениями?  ( Why cant php create a file even with 777 permissions ) 
У меня есть тестовый сервер виртуальной арки Linux с Xampp, работающим на моем ноутбуке, и я не могу получить PHP для создания новых файлов, даже с разрешения...

0  JQuery Mobile Link от PHP до HTML не работает, но URL делает изменения  ( Jquery mobile link from php to html not working but url does change ) 
Хорошо, так что когда я вошел в систему в свое приложение (index.html), я принимаю в login.php, отсюда я хочу меню для пользователя, но ни одна из моих ссылок...

3  Рассчитать размер плитки карты Google на уровне масштабирования N  ( Calculate tile size of google map at zoom level n ) 
Эй. Эй. У меня есть приложение MAPS, которое использует карты Google. Я получаю границы от карты, а затем я делаю некоторые кластеризащие маркеры на этой терр...

1  Разделение строки в номер телефона и расширение с помощью preg_match  ( Splitting a string into a phone number and extension using preg match ) 
Так что я пытаюсь разделить строку, которая содержит номер телефона и расширение, так как иногда существует расширение в строке. Это моя попытка: <код> $tes...

Связанный проблема

1  Как использовать URLFetch в PHP 
1  Экспорт Результат MySQL для Excel 
19  Как я могу получить простоту PHP (развертывание), но мощность Perl? 
21  Нарезка многомерного массива PHP через один из его элементов 
1  Запрос CURL PHP для ошибки возврата веб-службы 
0  Если запись в таблице A не существует в таблице b сделать что-то, как бы я пошел по этому поводу? 
6  CloudFlare API Перевести зависть в PHP Curl и отправить обновление CNAME 
2  Как загрузить OpenSSL.SO Динамическая библиотека в PHP 5.2.1 
0  Создание электронной почты на основе запроса MySQL 
1  PHP UNIX Время отсутствует Zeros 
0  Как я могу получить значение группы записей в группу столбца, используя с функцией в Laravel Eloquent ORM 
1  Почему PHP не может создать файл, даже с 777 разрешениями? 
0  JQuery Mobile Link от PHP до HTML не работает, но URL делает изменения 
3  Рассчитать размер плитки карты Google на уровне масштабирования N 
1  Разделение строки в номер телефона и расширение с помощью preg_match