in reply to Computer science Problem - single dimension bin packing

This sounds like the knapsack problem problem to me, which is indeed NP-hard. If you search CPAN for "knapsack", there's a few modules that may be of help.

That said, for many of these problems, it's only finding an optimal solution that's NP-hard (or worse). Finding a good solution may be much easier (speaking in terms of computational complexity), depending of course on the precise constraints on what constitutes a "good" solution.

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

Replies are listed 'Best First'.
Re^2: Computer science Problem - single dimension bin packing
by ikegami (Patriarch) on Aug 14, 2014 at 16:18 UTC
    The knapsack problem is different. You have a single bin, you are trying to maximize the total value of the items you place in the bin, each item having a size and value.
[reply]
Re^2: Computer science Problem - single dimension bin packing
by davis (Vicar) on Aug 14, 2014 at 16:14 UTC
    Thanks, I forgot to mention (sorry) I'd already looked at the knapsack problem... but I didn't see any mention of "multiple knapsacks". Frankly, though, that page is rather impenetrable to me because of phrases like "Dominance relations"...

    davis

[reply]

      The Wikipedia article has a section on that:

      Multiple knapsack problem

      This variation is similar to the Bin Packing Problem. It differs from the Bin Packing Problem in that a subset of items can be selected, whereas, in the Bin Packing Problem, all items have to be packed to certain bins. The concept is that there are multiple knapsacks. This may seem like a trivial change, but it is not equivalent to adding to the capacity of the initial knapsack. This variation is used in many loading and scheduling problems in Operations Research and has a PTAS.

      I'm afraid I'm not familiar with this variation, but having a name to search for should help, I reckon.

[reply]
        The OP surely wants to store the entire directory on his tapes. If so, MKP won't help. MKP is for when you have a fixed number of bins and stuff might not fit in the bins.
[reply]
      D'oh Although I still don't know if that's actually an answer!.

      davis

[reply]

In Section Seekers of Perl Wisdom