On 10/9/07, Jay Blanchard <[EMAIL PROTECTED]> wrote:
> [snip]
> This *IS* the knapsack problem. Just because you specify date ranges to
> get your values and the value isn't a knapsack doesn't change the fact
> that it is the same problem :) I remember having fun with genetic
> algorithms and the knapsack problem back in University.
> [/snip]
>
> You're right save for the knapsack problem considered not only volume,
> but value as well.
>
> --
> PHP General Mailing List (http://www.php.net/)
> To unsubscribe, visit: http://www.php.net/unsub.php
>
>
Keep in mind that I only wrote this in a few minutes just now, and
only for fun, so it's sloppy and not very well planned. In any case,
I hope it might be able to help you solve your problem, Jay....
(tested from the CLI because I'm in the middle of doing something else
right now)
<?
$v = $argv[1];
if(!$v) die("You must supply a value.\nUSAGE: php ".$argv[0]." AMOUNT\n");
$r[] = 3.98;
$r[] = 9.77;
$r[] = 3.76;
$r[] = 4.13;
$r[] = 7.86;
$r[] = 1.45;
$r[] = 12.87;
$r[] = 10.01;
$r[] = 0.88;
for($i=0;$i<count($r);$i++) {
$t = ($t + $r[$i]);
}
if($t < $v) {
die($v." is an illegal value, as ".$t." is the maximum
possible value, combining all known values!\n");
}
echo "The maximum value that could be returned for this array example
is ".$t."\n";
while(1) {
$done = False;
$try = 0;
unset($arr);
$attempts = rand(1,count($r));
for($i=0;$i<$attempts;$i++) {
$arr_hold = $r[rand(0,count($r))];
if($arr_hold < ($v - $try)) {
$try = ($try + $arr_hold);
$arr[] = $arr_hold;
if($try == $v) {
echo "Eureka! I've found the solution!\n";
$done = True;
break;
} elseif($try > $v) {
echo "Busted at ".$try."!\n";
$i = $attempts;
}
} else {
$i--;
}
}
if($done === True) {
break;
}
}
for($i=0;$i<count($arr);$i++) {
if($arr[$i]) {
if($final) {
$final .= "+";
}
$final .= "$arr[$i]";
}
}
echo $final." = ".$v."\n";
?>
--
Daniel P. Brown
[office] (570-) 587-7080 Ext. 272
[mobile] (570-) 766-8107
Give a man a fish, he'll eat for a day. Then you'll find out he was
allergic and is hospitalized. See? No good deed goes unpunished....
--
PHP General Mailing List (http://www.php.net/)
To unsubscribe, visit: http://www.php.net/unsub.php
