function knapSolveFast2($w, $v, $i, $aW, &$m) {

	global $numcalls;
	$numcalls ++;
	

	
	if (isset($m[$i][$aW])) {
		return array( $m[$i][$aW], $m['picked'][$i][$aW] );
	} else {

		
		if ($i == 0) {
			if ($w[$i] <= $aW) { 
				$m[$i][$aW] = $v[$i]; 
				$m['picked'][$i][$aW] = array($i); 
				return array($v[$i],array($i)); 

			} else {
				
				$m[$i][$aW] = 0; 
				$m['picked'][$i][$aW] = array(); 
				return array(0,array()); 
			}
		}	

		
		
		list ($without_i, $without_PI) = knapSolveFast2($w, $v, $i-1, $aW, $m);

		if ($w[$i] > $aW) { 

			$m[$i][$aW] = $without_i; 
			$m['picked'][$i][$aW] = $without_PI; 
			return array($without_i, $without_PI); 

		} else {

			
			list ($with_i,$with_PI) = knapSolveFast2($w, $v, ($i-1), ($aW - $w[$i]), $m);
			$with_i += $v[$i];  

			
			if ($with_i > $without_i) {
				$res = $with_i;
				$picked = $with_PI;
				array_push($picked,$i);
			} else {
				$res = $without_i;
				$picked = $without_PI;
			}

			$m[$i][$aW] = $res; 
			$m['picked'][$i][$aW] = $picked; 
			return array ($res,$picked); 
		}	
	}
}



$items4 = array(,,,,,,,,,,,,,,,,,,,,,);
$w4 = array(9,13,153,50,15,68,27,39,23,52,11,32,24,48,73,42,43,22,7,18,4,30);
$v4 = array(150,35,200,160,60,45,60,40,30,10,70,30,15,10,40,70,75,80,20,12,50,10);


$numcalls = 0; $m = array(); $pickedItems = array();


list ($m4,$pickedItems) = knapSolveFast2($w4, $v4, sizeof($v4) -1, 400, $m);


echo .join(,$items4).;
echo ;
echo .join(,$pickedItems).;


echo ;
echo ;
echo ;
$totalVal = $totalWt = 0;
foreach($pickedItems as $key) {
	$totalVal += $v4[$key];
	$totalWt += $w4[$key];
	echo .$items4[$key]..$v4[$key]..$w4[$key].;
}
echo ;
echo ;