95 lines
2.1 KiB
PHP
95 lines
2.1 KiB
PHP
#########################################################
|
|
# 0-1 Knapsack Problem Solve
|
|
# $w = weight of item
|
|
# $v = value of item
|
|
# $i = index
|
|
# $aW = Available Weight
|
|
# PHP Translation by Brian Berneker
|
|
#########################################################
|
|
|
|
function knapSolve($w,$v,$i,$aW) {
|
|
|
|
global $numcalls;
|
|
$numcalls ++;
|
|
// echo "Called with i=$i, aW=$aW<br>";
|
|
|
|
if ($i == 0) {
|
|
if ($w[$i] <= $aW) {
|
|
return $v[$i];
|
|
} else {
|
|
return 0;
|
|
}
|
|
}
|
|
|
|
$without_i = knapSolve($w, $v, $i-1, $aW);
|
|
if ($w[$i] > $aW) {
|
|
return $without_i;
|
|
} else {
|
|
$with_i = $v[$i] + knapSolve($w, $v, ($i-1), ($aW - $w[$i]));
|
|
return max($with_i, $without_i);
|
|
}
|
|
|
|
}
|
|
|
|
|
|
#########################################################
|
|
# 0-1 Knapsack Problem Solve (with "memo"-ization optimization)
|
|
# $w = weight of item
|
|
# $v = value of item
|
|
# $i = index
|
|
# $aW = Available Weight
|
|
# $m = 'memo' array
|
|
# PHP Translation by Brian Berneker
|
|
#########################################################
|
|
|
|
function knapSolveFast($w,$v,$i,$aW,&$m) { // Note: We use &$m because the function writes to the $m array
|
|
|
|
global $numcalls;
|
|
$numcalls ++;
|
|
// echo "Called with i=$i, aW=$aW<br>";
|
|
|
|
// Return memo if we have one
|
|
if (isset($m[$i][$aW])) {
|
|
return $m[$i][$aW];
|
|
} else {
|
|
|
|
if ($i == 0) {
|
|
if ($w[$i] <= $aW) {
|
|
$m[$i][$aW] = $v[$i]; // save memo
|
|
return $v[$i];
|
|
} else {
|
|
$m[$i][$aW] = 0; // save memo
|
|
return 0;
|
|
}
|
|
}
|
|
|
|
$without_i = knapSolveFast($w, $v, $i-1, $aW,$m);
|
|
if ($w[$i] > $aW) {
|
|
$m[$i][$aW] = $without_i; // save memo
|
|
return $without_i;
|
|
} else {
|
|
$with_i = $v[$i] + knapSolveFast($w, $v, ($i-1), ($aW - $w[$i]),$m);
|
|
$res = max($with_i, $without_i);
|
|
$m[$i][$aW] = $res; // save memo
|
|
return $res;
|
|
}
|
|
}
|
|
}
|
|
|
|
|
|
$w3 = array(1, 1, 1, 2, 2, 2, 4, 4, 4, 44, 96, 96, 96);
|
|
$v3 = array(1, 1, 1, 2, 2, 2, 4, 4, 4, 44, 96, 96, 96);
|
|
|
|
$numcalls = 0;
|
|
$m = array();
|
|
$m3 = knapSolveFast($w3, $v3, sizeof($v3) -1, 54,$m);
|
|
print_r($w3); echo "<br>FAST: ";
|
|
echo "<b>Max: $m3</b> ($numcalls calls)<br><br>";
|
|
|
|
|
|
$numcalls = 0;
|
|
$m = array();
|
|
$m3 = knapSolve($w3, $v3, sizeof($v3) -1, 54 );
|
|
print_r($w3); echo "<br>";
|
|
echo "<b>Max: $m3</b> ($numcalls calls)<br><br>";
|