#codeifyoucansolve
PHP CLI Implementation of 0-1 Knapsack Problem.
T : testcase
N : number of next line input of price and weight
P : weight
Input Format
T
N P
Price Weight

Input
2
2 50
80 40
60 20
5 100
100 40
40 50
50 40
60 20
100 40
Output
80
260

<?php
fscanf(STDIN,"%d\n",$T);
while($T--)
{
 $str = trim(fgets(STDIN));
 $str = explode(" ",$str);
 $N = intval($str[0]);
 $P = intval($str[1]);
 $x = array();
 $y = array();
 while($N--)
 {
 $str = trim(fgets(STDIN));
 $str = explode(" ",$str);
 $x[] = intval($str[0]);
 $y[] =   intval($str[1]);
 }
 $k = array();
 for($i=0;$i<=count($x);$i++)
 {
 for($j=0;$j<=$P;$j++)
 {
 if($i===0 || $j ===0)
   $k[$i][$j]=0;
 else if($y[$i-1]<=$j)
  {
   $a = $x[$i-1]+$k[$i-1][$j-$y[$i-1]];
   $k[$i][$j]=($a>$k[$i-1][$j])?$a:$k[$i-1][$j];
  }
  else
    $k[$i][$j] = $k[$i-1][$j];
 }
 }
 print($k[count($x)][$P]."\n");
 
}

?>

http://ideone.com/Tfz3by