writer Posted April 4, 2008 Share Posted April 4, 2008 Has anyone seen a version of this executed in PHP? Link to comment https://forums.phpfreaks.com/topic/99495-backpack-problem/ Share on other sites More sharing options...
947740 Posted April 18, 2008 Share Posted April 18, 2008 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. Link to comment https://forums.phpfreaks.com/topic/99495-backpack-problem/#findComment-520380 Share on other sites More sharing options...
writer Posted April 21, 2008 Author Share Posted April 21, 2008 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. Link to comment https://forums.phpfreaks.com/topic/99495-backpack-problem/#findComment-522429 Share on other sites More sharing options...
moon 111 Posted April 21, 2008 Share Posted April 21, 2008 The knapsack problem has already 'solved'. All you have to do is turn it into PHP code. Link to comment https://forums.phpfreaks.com/topic/99495-backpack-problem/#findComment-522638 Share on other sites More sharing options...
writer Posted April 21, 2008 Author Share Posted April 21, 2008 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; } Link to comment https://forums.phpfreaks.com/topic/99495-backpack-problem/#findComment-522885 Share on other sites More sharing options...
Barand Posted April 21, 2008 Share Posted April 21, 2008 <?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; } ?> Link to comment https://forums.phpfreaks.com/topic/99495-backpack-problem/#findComment-522992 Share on other sites More sharing options...
writer Posted April 23, 2008 Author Share Posted April 23, 2008 Wow, thanks Barand! Now how would I implement this? My guess: $n = new knack ($cap, $start) Link to comment https://forums.phpfreaks.com/topic/99495-backpack-problem/#findComment-525356 Share on other sites More sharing options...
Barand Posted April 23, 2008 Share Posted April 23, 2008 echo knack ($cap, $start) Link to comment https://forums.phpfreaks.com/topic/99495-backpack-problem/#findComment-525524 Share on other sites More sharing options...
Recommended Posts
Archived
This topic is now archived and is closed to further replies.