Re: Looking for help with a complex algorithm

["Daniel Brown" <parasane@xxxxxxxxx>]

On 10/9/07, Jay Blanchard <jblanchard@xxxxxxxxxx> 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