Hi,
I'm trying to implement an unbounded knapsack problem.
It works just fine, in it's classic form (need to find the maximum
benefit by taking total weights < capacity of knapsack). However I
need it a little bit changed -- I need to find the minimum benefit
instead of maximum. If I try just to change the condition (from max to
min), I get some kind of minimum value but it doesn't fill all the
"knapsack". I need it to be filled.
Here's the classic code (it's written in PHP). If anyone has an idea
how to change, please let me know. Thank you.
// weight and value
$w = array(0 ,1, 3, 5);
$v = array(0, 5.2, 14.555, 23.10);
// total volume
$n = 6;
$weight[0] = 0;
for ($i = 1; $i <= $n; ++$i)
{
$max = -PHP_INT_MAX;
for ($j = 1; $j <= 3; ++$j)
if ($i - $w[$j] >= 0)
if ($v[$j] + $weight[$i - $w[$j]] > $max)
{
$max = $v[$j] + $weight[$i - $w[$j]];
$item = $j;
}
$weight[$i] = $max;
$path[$i] = $item;
}
while ($n > 0)
{
echo $path[$n];
$n -= $w[$path[$n]];
}
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected]
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~----------~----~----~----~------~----~------~--~---
