Re: array_sum($result)=100

["Ahmad Al-Twaijiry" <ahmadt@xxxxxxxxx>]

Finally I found a solution :)  Thanks to Mr. Phil Rogaway

I found a very small C++ code from Mr. Phil Rogaway in
http://www.cs.ucdavis.edu/~rogaway/classes/122A/spring00/prog1.C

I convert it to php and here is the result  (I already test it, try it
and let me know if you find any bug):

//code #1 it will print the result to stdout:
<?php
// prog2.php
//
// Subset sum demonstration code.
// Written for ECS 122a by Phil Rogaway (Spring 2000)
//
// http://www.cs.ucdavis.edu/~rogaway/classes/122A/spring00/prog1.C
// converted to php by Ahmad AlTwaijiry (ahmadt "at" gmail.com) 25/Sep/2006
$price = 40;
$list = array(0,3,2,3,6,2,120,11,220,11,22,10,2,5,7,1,4,20,40);
SubsetSUM($price,$list);
function PrintSolution($A, $i,$list)
{
 if ($i==0) return;
 else if ($i<0) print "ERROR\n";
 else if ($A[$i]==-1) print "No Solution Possible\n";
 else {PrintSolution($A, $i-$list[$A[$i]],$list);
       print "Take item " . $A[$i] . " (which is " . $list[$A[$i]] . ")\n";}
}


function SubsetSUM($price,$list)
{
 $A=array();
 $N=sizeof($list)-1;
 print "Subset Sum Demonstration Code\n\n";

 print  "The array is [ ";
 for ($i=1; $i<=$N; $i++) print  "(".$list[$i] . ") ";
 print "] and the target value is " . $price . "\n\n";

 //
 // OK, here it is!
 //
 for ($b=1; $b<=$price; $b++) $A[$b] = -1;
 for ($n=1; $n<=$N; $n++) {
   for ($b=$price; $b>=1;$b--) {
     if ($A[$b]==-1 &&
        ($b==$list[$n] || ($list[$n]<$b && $A[$b-$list[$n]]!=-1))) $A[$b]=$n;
   }
 }

 PrintSolution($A, $price,$list);
 print "\n";
}
?>

//code #2 it will return the result as array (so you can use it in your code) :

<?php
// prog3.php
//
// Subset sum demonstration code.
// Written for ECS 122a by Phil Rogaway (Spring 2000)
//
// http://www.cs.ucdavis.edu/~rogaway/classes/122A/spring00/prog1.C
// converted to php by Ahmad AlTwaijiry (ahmadt "at" gmail.com) 25/Sep/2006
$price = 50;
$list = array(0,3,2,3,6,2,120,11,220,11,22,10,2,5,7,1,4,20,40);
$result = SubsetSUM($price,$list);
if(is_array($result)) {
print_r($result);
}else {
print "->$result\n";
}
function PrintSubsetSUM($A, $i,$list,$result, $limit=30)
{
 static $max_recursive = 0;
 //if we call function PrintSubsetSUM more than $limit then return null
 if ( $max_recursive > $limit ) { $result ="Reached $limit"; return; }
 $max_recursive++;
 if ($i==0) return;
 else if ($i<0) { $result = "ERROR"; return; }
 else if ($A[$i]==-1) { $result= "No Solution"; return;}
 else { PrintSubsetSUM($A, $i-$list[$A[$i]],$list,&$result);
       $result[$A[$i]] = $list[$A[$i]];}
}
function SubsetSUM($price,$list)
{
 $A=array();
 $N=sizeof($list)-1;
 $result = array();
 for ($b=1; $b<=$price; $b++) $A[$b] = -1;
 for ($n=1; $n<=$N; $n++) {
   for ($b=$price; $b>=1;$b--) {
     if ($A[$b]==-1 &&
        ($b==$list[$n] || ($list[$n]<$b && $A[$b-$list[$n]]!=-1))) $A[$b]=$n;
   }
 }
 PrintSubsetSUM($A, $price,$list,&$result);
 return $result;
}
?>


On 9/25/06, Ahmad Al-Twaijiry <ahmadt@xxxxxxxxx> wrote:
> Robin,
> you made it harder for me specially with wikipedia artical :) (I told
> you I'm bad with writing code from English paragraph)
> and no it's not a homework (btw: do they allow php in school ?, I
> remember we use basic :) )
>
> anyway I will try to write the code and I will let you guys know (in
> the mean time if someone can help me in anyway I really appreciate it)
>
>
> On 9/25/06, Robert Cummings <robert@xxxxxxxxxxxxx> wrote:
> > On Mon, 2006-09-25 at 16:42 +0100, Robin Vickery wrote:
> > > On 24/09/06, Ahmad Al-Twaijiry <ahmadt@xxxxxxxxx> wrote:
> > > > Hi everyone
> > > >
> > > > I have array of numbers and I want to get out of it a list of numbers
> > > > that if I sum them it will be 100, here is my list (for example ) :
> > > >
> > > > $list = array(10,20,10,10,30,50,33,110,381,338,20,11,200,100);
> > > >
> > > >
> > > > I want the result to be :
> > > >
> > > > $result = array( 10,20,10,10,50);
> > > >
> > > > as you can see in the array $result , if we array_sum($result) the
> > > > result will be 100.
> > > >
> > > > is they any algorithm to do this ?
> > >
> > > Ah, the Subset Sum Problem - this isn't school homework by any chance?
> > >
> > > http://en.wikipedia.org/wiki/Subset_sum_problem
> >
> > Cool, I didn't know it had a specific name, all I could think of was
> > that it sounded a lot like the knapsack problem. The Wikipedia article
> > indicates it's a special case of the knapsack problem.
> >
> > Cheers,
> > Rob.
> > --
> > .------------------------------------------------------------.
> > | InterJinn Application Framework - http://www.interjinn.com |
> > :------------------------------------------------------------:
> > | An application and templating framework for PHP. Boasting  |
> > | a powerful, scalable system for accessing system services  |
> > | such as forms, properties, sessions, and caches. InterJinn |
> > | also provides an extremely flexible architecture for       |
> > | creating re-usable components quickly and easily.          |
> > `------------------------------------------------------------'
> >
> > --
> > PHP General Mailing List (http://www.php.net/)
> > To unsubscribe, visit: http://www.php.net/unsub.php
> >
> >
>
>
> --
>
> Ahmad Fahad AlTwaijiry


--

Ahmad Fahad AlTwaijiry

--
PHP General Mailing List (http://www.php.net/)
To unsubscribe, visit: http://www.php.net/unsub.php