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++;
	}
 }

?>

скачать код