more useful options PerlMonks

### Re^2: Computer science Problem - single dimension bin packing

by ikegami (Pope)
 on Aug 14, 2014 at 17:08 UTC ( #1097452=note: print w/replies, xml ) Need Help??

What are you trying to optimize?

Neither. It's one of

• If he has an unlimited number of tapes: Minimize the number of tapes needed (bin packing problem).
• If he has an limited number of tapes: Maximize the value of what will fit on the tapes he has (multiple knapsack problem).

Efficiently fill drives of fixed size? The latter is (as AppleFritter points out) the knapsack problem.

No, it's not, as I already pointed out. In the knapsack problem, you have one bin (tape), and you're trying the maximize what you can put on it. Stuff is left behind.

• Comment on Re^2: Computer science Problem - single dimension bin packing

Replies are listed 'Best First'.
Re^3: Computer science Problem - single dimension bin packing
by FloydATC (Deacon) on Aug 14, 2014 at 18:29 UTC
Stuff is left behind.

Then add another bin (tape) and start filling it with leftovers. Repeat until no more bins (tapes) or leftovers.

The first few bins would probably be most optimally filled for most datasets but if the goal is to use the least amount of tapes this should work... or am I missing something?

-- FloydATC

Time flies when you don't know what you're doing

Then add another bin (tape) and start filling it with leftovers. Repeat until no more bins (tapes) or leftovers.

That wouldn't optimize anything. I think we all agree that there is something that he wants to optimize.

That wouldn't optimize anything

What I mean is, it's still a knapsack problem but there are fewer items with each iteration. In pseudocode:

```my @items = qw( loads of variable size items here );
while (@items) {
push @tapes, remove_from(\@items);
}

sub remove_from {
my \$arrayref = shift;
my \$taperef = [];

# Knapsack algorithm goes here
# ...

# Whatever we put in \$taperef is removed from \$arrayref
# ...

return \$taperef;
}

How would this not optimize for number of tapes?

-- FloydATC

Time flies when you don't know what you're doing

Re^3: Computer science Problem - single dimension bin packing
by kennethk (Abbot) on Aug 14, 2014 at 18:03 UTC

Except that the original problem description does not include the size of the tapes, which means it doesn't clearly map to either of your suggestions. Thus my attempt to gather more data.

#11929 First ask yourself `How would I do this without a computer?' Then have the computer do it the same way.

Create A New User
Node Status?
node history
Node Type: note [id://1097452]
help
Chatterbox?
 [markong]: ahah thanks Corion :) [Eily]: Discipulus usually it's while testing that you want the full logs :) [Eily]: anyway, maybe you can ignore STDERR ? (I'm not sure about @CARP_NOT, it looks like it only changes the place the error comes from) [markong]: " Perl: the Markov chain saw" :D aha [Discipulus]: thanks 1nickt but seems i'm not able to use it correctly... [Discipulus]: Eily i'm testing a failure: i ok if i get bad results.. perhaps there is another way to do it...

How do I use this? | Other CB clients
Other Users?
Others making s'mores by the fire in the courtyard of the Monastery: (6)
As of 2018-01-22 11:26 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
How did you see in the new year?

Results (233 votes). Check out past polls.

Notices?