Re: [PHP] array_sum($result)=100
Hi, This seems to be nice method, I tried to do translate it to PHP put since I'm bad in English I couldn't :) could you give me some prototype for the method. On 9/25/06, Google Kreme [EMAIL PROTECTED] wrote: On 24 Sep 2006, at 10:41 , Penthexquadium wrote: On Sun, 24 Sep 2006 19:06:11 +0300, Ahmad Al-Twaijiry [EMAIL PROTECTED] wrote: 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 ) : I think you can try to sort the array in reverse order, and then calculate the sum of numbers in loops (end loop when the sum is larger than target sum). That seems like a very slow way to do it, I think. First thing, sort the array, then scan the array backwards for the first number under the target sum (in this case, 50). Then look for another number that will add to make the target sum. So, if you find a 90, look for a 10. If you find it, you're done. If you don't find it, then search for the next smallest number (33) and add it. Then repeat. If you don't find a match at 83, then add the next smallest number, 20. But that puts you over your target, so you discard 33 and start over with 50 and the next lowest number, 20. Now you are only looking for numbers =20. This might be the perfect place to use a recursive function, as long as you are careful to limit it's iteration cycles. No way is this going to be done quickly. -- And, while it was regarded as pretty good evidence of criminality to be living in a slum, for some reason owning a whole street of them merely got you invited to the very best social occasions. -- PHP General Mailing List (http://www.php.net/) To unsubscribe, visit: http://www.php.net/unsub.php -- Ahmad Fahad AlTwaijiry -- PHP General Mailing List (http://www.php.net/) To unsubscribe, visit: http://www.php.net/unsub.php
Re: [PHP] array_sum($result)=100
On 24/09/06, Ahmad Al-Twaijiry [EMAIL PROTECTED] 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 -robin -- PHP General Mailing List (http://www.php.net/) To unsubscribe, visit: http://www.php.net/unsub.php
Re: [PHP] array_sum($result)=100
2006/9/25, Robin Vickery [EMAIL PROTECTED]: On 24/09/06, Ahmad Al-Twaijiry [EMAIL PROTECTED] 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? You're surely mistaken, there are many practical uses of the subset sum problem in website development, like errr... shipping optimization!
Re: [PHP] array_sum($result)=100
On Mon, 2006-09-25 at 16:42 +0100, Robin Vickery wrote: On 24/09/06, Ahmad Al-Twaijiry [EMAIL PROTECTED] 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
Re: [PHP] array_sum($result)=100
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 [EMAIL PROTECTED] wrote: On Mon, 2006-09-25 at 16:42 +0100, Robin Vickery wrote: On 24/09/06, Ahmad Al-Twaijiry [EMAIL PROTECTED] 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 -- PHP General Mailing List (http://www.php.net/) To unsubscribe, visit: http://www.php.net/unsub.php
Re: [PHP] array_sum($result)=100
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 ($i0) 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 ($i0) { $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 [EMAIL PROTECTED] 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 [EMAIL PROTECTED] wrote:
On Mon, 2006-09-25 at 16:42 +0100, Robin Vickery wrote:
On 24/09/06, Ahmad Al-Twaijiry [EMAIL PROTECTED] 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
Re: [PHP] array_sum($result)=100
At 1:50 PM -0300 9/25/06, Martin Alterisio wrote: 2006/9/25, Robin Vickery [EMAIL PROTECTED]: On 24/09/06, Ahmad Al-Twaijiry [EMAIL PROTECTED] 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? You're surely mistaken, there are many practical uses of the subset sum problem in website development, like errr... shipping optimization! Don't forget real world problems like when my wife gives me $100, a shopping list, and says bring back as many items as you can. Or when I take all 10 grand-kids to McDonald's and try to buy each kid as much as I can with $20 -- my vector calculus classes in grad school didn't prepare me for that high level math. :-) tedd -- --- http://sperling.com http://ancientstones.com http://earthstones.com -- PHP General Mailing List (http://www.php.net/) To unsubscribe, visit: http://www.php.net/unsub.php
[PHP] array_sum($result)=100
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 ? -- PHP General Mailing List (http://www.php.net/) To unsubscribe, visit: http://www.php.net/unsub.php
Re: [PHP] array_sum($result)=100
On Sun, 24 Sep 2006 19:06:11 +0300, Ahmad Al-Twaijiry [EMAIL PROTECTED] 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 ? I think you can try to sort the array in reverse order, and then calculate the sum of numbers in loops (end loop when the sum is larger than target sum). It seems there is no algorithm can do this quickly. -- PHP General Mailing List (http://www.php.net/) To unsubscribe, visit: http://www.php.net/unsub.php
Re: [PHP] array_sum($result)=100
On 24 Sep 2006, at 10:41 , Penthexquadium wrote: On Sun, 24 Sep 2006 19:06:11 +0300, Ahmad Al-Twaijiry [EMAIL PROTECTED] wrote: 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 ) : I think you can try to sort the array in reverse order, and then calculate the sum of numbers in loops (end loop when the sum is larger than target sum). That seems like a very slow way to do it, I think. First thing, sort the array, then scan the array backwards for the first number under the target sum (in this case, 50). Then look for another number that will add to make the target sum. So, if you find a 90, look for a 10. If you find it, you're done. If you don't find it, then search for the next smallest number (33) and add it. Then repeat. If you don't find a match at 83, then add the next smallest number, 20. But that puts you over your target, so you discard 33 and start over with 50 and the next lowest number, 20. Now you are only looking for numbers =20. This might be the perfect place to use a recursive function, as long as you are careful to limit it's iteration cycles. No way is this going to be done quickly. -- And, while it was regarded as pretty good evidence of criminality to be living in a slum, for some reason owning a whole street of them merely got you invited to the very best social occasions. -- PHP General Mailing List (http://www.php.net/) To unsubscribe, visit: http://www.php.net/unsub.php
