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 algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---