<?php
/*
 * Created on 11.08.2011 by Sergey Fedorenko
 */
 
 
 class Cutter {
   
    public  $the_best_tail;
    private $m_units = array();
   
    public $m_best_units = array();
    public $m_best_tails = array();
   
    public $m_best_result;
    public $m_best_store=array();
    public $m_best_store_tail=array();

    public $a_best_result;
    public $a_best_store=array();
    public $a_best_store_tail=array();
   
    public function SetStore($store) {  $this->m_store=$store; }
    public function SetUnits($units) {  $this->m_units=$units; }
   
    public function SwapUnits($key1,$key2) { $tmp=$this->m_units[$key1]; $this->m_units[$key1]=$this->m_units[$key2]; $this->m_units[$key2]=$tmp; }
   
    public function Review() {
//          echo "\n-------"; foreach($this->m_units as $k => $val) {echo $val." ";} echo "-------";
        $m_units_used=array_fill ( 0 , count($this->m_units), 0 );
       
        $num_units=count($this->m_units);

        $summ_tails=0;
       
        $index_result=0;
        do {
            $best_tail=1000000;
           
            foreach ($this->m_store as $s_key => $s_value) {
               
                $tail=$s_value;
                $temp_units_used=$m_units_used;
           
                foreach ($this->m_units as $u_key => $u_value) {
                   
                    if($m_units_used[$u_key]==1) continue;
                   
                    if($tail>$u_value) {
                        $tail-=$u_value;
                        $temp_units_used[$u_key]=1;                    
                    }
                }
                if($tail<$best_tail) {
                    $best_tail=$tail;
                    $best_storekey=$s_key;
                    $best_units_used=$temp_units_used;

                    $this->m_best_store[$index_result]=$this->m_store[$s_key];
                    $add_index=0;
                    unset($this->m_best_result[$index_result]);
//                  echo "\n".$index_result." Best:".$this->m_store[$s_key]."   tail:".$tail;
                    foreach ($this->m_units as $u_key => $u_value) {
                        if($temp_units_used[$u_key]==$m_units_used[$u_key] || $temp_units_used[$u_key]!=1) continue;
                        $this->m_best_result[$index_result][$add_index]=$u_value;
//                      echo " ".$u_value;
                        $add_index++;
                    }
                    $this->m_best_store_tail[$index_result]=$tail;
                }
            }
            //нашли лучший вариант (какую из заготовок брать)
            $m_units_used=$best_units_used;
            $summ_tails+=$best_tail;
            $last_tail=$best_tail;
           
//          echo "\n----------".array_sum($m_units_used)."<".$num_units;
            $index_result++;
        }
        while(array_sum($m_units_used)<$num_units);

        return $summ_tails-$last_tail;
    }
   
   
    public function FindTheBest( $limit_iterations) {
       
       rsort($this->m_units,SORT_NUMERIC);
       $u_len=count($this->m_units);

       $this->the_best_tail=1000000000;
       for( $iter=0; $iter<$limit_iterations; $iter++) {
       
         unset($this->m_best_result);
         unset($this->m_best_store);
         unset($this->m_best_store_tail);
         
         $this_tail=$this->Review();
         
         if($this_tail<$this->the_best_tail) {
            $this->the_best_tail=$this_tail;
           
           
            $this->a_best_result    =$this->m_best_result;
            $this->a_best_store     =$this->m_best_store;
            $this->a_best_store_tail=$this->m_best_store_tail;
         }
         
         shuffle($this->m_units);
         //$this->SwapUnits(rand(0,$u_len-1),rand(0,$u_len-1));
         
       }
    }
   
 }
 
 //--------------- how to use -----------------
 
// $detal = array(56,151,234,387,4729,587,46,1568,823,214,765,2634,1845,1733,936,631,1936,2190,2184,1439,56,151,234,387,4729,587,46,1568,823,214,765,2634,1845,1733,936,631,1936,2190,2184,1439);
 $zagot = array(3000, 6000);
 $detal = array(56,151,234,387,4729,587,46,1568,823,214,765,2634,1845,1733,936,631,1936,2190,2184,1439);
 
 $the_cutter=new Cutter();
 $the_cutter->SetStore($zagot);
 $the_cutter->SetUnits($detal);
 $the_cutter->FindTheBest(1000);

    foreach($the_cutter->a_best_store as $i => $val) {
        echo "\n Заготовка:".$val." ( ";
        foreach( $the_cutter->a_best_result[$i] as $unit) {
            echo $unit." ";
        }
        echo ")  Остаток:".$the_cutter->a_best_store_tail[$i];
    }
    echo "\nСуммарный остаток (без последнего):".$the_cutter->the_best_tail;
 
?>

Вот результат работы программы:

 Заготовка:6000 ( 56 1936 1439 214 2190 151 )  Остаток:14
 Заготовка:6000 ( 2634 765 1568 936 46 )  Остаток:51
 Заготовка:6000 ( 1733 2184 1845 234 )  Остаток:4
 Заготовка:6000 ( 823 4729 387 )  Остаток:61
 Заготовка:6000 ( 587 631 )  Остаток:4782
Суммарный остаток (без последнего):130

Время работы — меньше секунды на 1000 вариантах