this would require a recalculation of the @weights and $total after each pick in order to avoid getting the same pick repeatedly

Yes, but:

1. Recalculating the total is: $total -= $weights[ $pick ]; which is hardly onerous.
2. Recalculating @weights is just: $weights[ $pick ] = 0;

   If you set the weight of the previous pick to 0, it'll never get picked again.

So, to pick them all in a random order, you pick the first, subtract its weight from the total, set it weight to 0 and pick again. Repeat for N:

sub pickAll{
    my @weights = @_;
    my $total = sum @weights;
    my @order;
    for( 0 .. $#_ ) {
        my $pick = pick( \@weights, $total );
        push @order, $pick;
        $total -= $weights[ $pick ];
        $weights[ $pick ] = 0;
    }
    return @order;
}
[download]

Putting it all together you get:

#! perl -slw
use strict;
use List::Util qw[ sum ];

our $SHIPS ||= 10;
our $REPS ||= 1e5;

sub pick {
    my( $weights, $total ) = @_;
    my $rand = rand $total;
    ( $rand -= $weights->[ $_ ] ) < 0 
        and return $_ for 0 .. $#$weights;
}

sub pickAll{
    my @weights = @_;
    my $total = sum @weights;
    my @order;
    for( 0 .. $#_ ) {
        my $pick = pick( \@weights, $total );
        push @order, $pick;
        $total -= $weights[ $pick ];
        $weights[ $pick ] = 0;
    }
    return @order;
}

my @weights = map rand( 16 ), 1 .. $SHIPS;
print "$_ : $weights[ $_ ]" for 0 .. $#weights;

my $total = sum @weights;

print "\n";

print join ' ', pickAll( @weights ) for 1 .. $REPS;
[download]

I just spent a couple of hours trying to work out how to demonstrate that this results in a properly weighted distribution, but it's beyond me today. But by cherry picking a couple of runs, I think you can see it at work:

In this run you can see that ship 1 has a much lower weighting whilst the other three are very similar. With the result that the first ships 0,2 & 3 are pretty evenly distributed in the first 3 places, and ship 1 is (almost) always picked last:

C:\test>WeightedPick.pl -SHIPS=4 -REPS=30
0 : 14.4176797792315
1 : 1.80334489420056
2 : 14.493153475225
3 : 14.258566647768

3 2 0 1
3 0 2 1
0 3 2 1
0 3 1 2
0 3 2 1
0 2 3 1
3 2 0 1
0 2 3 1
3 0 2 1
1 0 3 2
3 2 0 1
3 0 2 1
0 3 2 1
3 0 2 1
3 0 2 1
0 2 3 1
3 1 2 0
2 3 0 1
2 0 3 1
3 2 0 1
0 3 2 1
2 3 0 1
3 0 2 1
3 2 0 1
2 3 0 1
2 3 1 0
3 0 2 1
0 2 1 3
3 2 0 1
0 2 3 1
[download]

In this run, ship 3 is weighted roughly twice ship 1 which is roughly twice ship 2; whilst ship 0 is almost not there. With the result that the first two picks are mostly 1s and 3s; the 3rd pick is mostly 2s and the last pick mostly 0s:

C:\test>WeightedPick.pl -SHIPS=4 -REPS=30
0 : 0.762649480253458
1 : 10.0145217105746
2 : 6.81761548668146
3 : 15.7317210100591

1 3 2 0
1 2 3 0
2 1 3 0
3 1 2 0
3 2 1 0
2 1 3 0
3 1 2 0
1 3 2 0
3 1 2 0
1 2 3 0
1 3 2 0
1 3 2 0
3 1 2 0
1 3 2 0
1 3 2 0
2 1 3 0
2 3 1 0
1 3 2 0
3 1 2 0
2 3 1 0
2 3 1 0
1 2 3 0
3 1 2 0
3 1 2 0
2 3 1 0
3 1 2 0
2 3 1 0
1 3 0 2
3 1 2 0
3 1 2 0
[download]

If any of the math gurus want to show me how to check the distributions arithmetically, I'm all ears :)

Also, I think the big-O rating is: O( 2n + n(n-1)/4 ). Can anyone verify that for me?