LiveStreet

Сделал скрипит, который выбирает продукты по заданному кол-ву денег. Но учитывается, чтобы вес (цена) продукта был как можно больше и чтобы потратили всё до копейки. Использовал динамическое программирование, т.е. разбил задачу на под задачи. Алгоритм которые использовал, называется «Банкомат».

Опишу сердце скрипта:

<?php
$simple2IdLeft=$_GET['simple2IdLeft'];

$MAX=1000000000; //если не можем потратить всё до копейки
$n=$simple2IdLeft; // деньги клиента 
$k=10; //кол-во наших товаров
        
//очень важна сортировка, если например мы их из бд выбираем
//вес (цена) товара
$a[0]=1;
$a[1]=5;        
$a[2]=10;
$a[3]=60;
$a[4]=100;
$a[5]=180;
$a[6]=250;
$a[7]=550;
$a[8]=1000;
$a[9]=1500;
        
//название продуктов
$product[$a[0]]="мороженое";    
$product[$a[1]]="футболка";
$product[$a[2]]="дыня";
$product[$a[3]]="мячик";
$product[$a[4]]="мышка";        
$product[$a[5]]="велосипед";
$product[$a[6]]="мопед";
$product[$a[7]]="компьютер";
$product[$a[8]]="машина";       
$product[$a[9]]="инвайт на Хабр!";      
        
        for ($m=1;$m<=$n;++$m) //помечаем, что F[m] выдать нельзя
        {
                $F[$m]=$MAX;
                for ($i=0;$i<$k;++$i) //перебираем номиналы банкнот
                {
                        if ($m>=$a[$i] && $F[$m-$a[$i]]+1<$F[$m]) 
                        {
                                $F[$m]=$F[$m-$a[$i]]+1; //изменяем значения, если нашли лучший выбор
                        }
                }
        }
        $m=0;
print "Ваша сумма: <b><font color='green'>".$simple2IdLeft."</font></b>
";      
 if ($F[$simple2IdLeft]==$MAX || $simple2IdLeft==0) 
 {
        print "<font color='red'>Пробуй другие значения</font>"; //не можем потратить всё до копейки
 }
 else 
 { 
   print "<i>
На эту сумму вы можете купить:</i>"; 
   while($n>0) 
   {
     for($i=0;$i<$k;++$i) //бежим по номиналам
        {
                   if($F[$n-$a[$i]]==$F[$n]-1) //наш товар
                   { 
                                $answer[$m]=$product[$a[$i]]; 
                                $n-=$a[$i];     
                                $m++;                           
                                break; 
                   } 
     } 
   }
 }
$cnt=1;
//простой вывод и сразу считаем кол-во товара в штуках
 for ($i=1;$i<=$m;$i++)
 {
        if ($answer[$i-1]!=$answer[$i])
        {
                print $cnt." шт.  - ".$answer[$i-1];
                $cnt=1;
        }
        else
        {
                $cnt++;
        }
 }

?>

скачать код