Backpack problem

[writer]

Has anyone seen a version of this executed in PHP?

[947740]

I, personally, I have never seens anything about that.  After looking at the page you provided it looks "doable", but I am not quite sure on some of the computations.

[writer]

Aha! A reply!

 

I've heard of it being done at an academic level using JS, but at the time didn't have any programming knowledge.

[moon 111]

The knapsack problem has already 'solved'. All you have to do is turn it into PHP code.

[writer]

I should be able to get an approx. answer if I can convert this to PHP:

 

int knack(int cap, int start) 
{ 
for(int i=start, max=0;i<N;i++) 
{ 
	int space=cap-item[i].size;
	if(space >= 0) 
	{ 
		int t = knack(space, i+1)+item[i].val; 
		if(t>max) 
		{
			max=t; 
		}
	}
} 
return max; 
}

[Barand]

<?php
define ("N", 3);                       // define constant N

$item = array (                                             // define the items
               array ('size' => 2, 'val' => 6),
               array ('size' => 4, 'val' => 2),
               array ('size' => 3, 'val' => 4)
              );

function knack($cap, $start)                         
{ 
global $item;
    
    for($i=$start, $max=0; $i<N; $i++) 
{ 
	$space=$cap-$item[$i]['size'];
	if($space >= 0) 
	{ 
		$t = knack($space, $i+1)+$item[$i]['val']; 
		if($t>$max) 
		{
			$max=$t; 
		}
	}
} 
return $max; 
}
?>

[writer]

Wow, thanks Barand!

 

Now how would I implement this? My guess:

 

$n = new knack ($cap, $start)

 

 

 

[Barand]

echo  knack ($cap, $start)