使用Algorithm-Bucketizer时超桶容物品被排除，求替代算法

Great question! The issue you're running into with Algorithm::Bucketizer is a pretty common limitation of standard bin packing implementations—they often assume all items can fit within the defined bucket capacity, so anything bigger gets tossed out. Let’s go through some practical solutions to handle those oversized items without losing track of them:

1. Add Custom Pre-Processing to Your Current Workflow #

If you want to stick with Algorithm::Bucketizer, you can easily add a pre-step to separate oversized items and handle them manually before running the main packing logic. Here’s a quick example:

my @items = (
    { id => 'A', weight => 15 },
    { id => 'B', weight => 23 },
    { id => 'C', weight => 10 },
    { id => 'D', weight => 8 },
    { id => 'E', weight => 88 },
);
my $bucket_capacity = 30;

# Split items into those that fit and those that don't
my (@oversized, @fit_items);
foreach my $item (@items) {
    if ($item->{weight} > $bucket_capacity) {
        push @oversized, $item;
    } else {
        push @fit_items, $item;
    }
}

# Run Bucketizer on items that fit
my $bucketizer = Algorithm::Bucketizer->new(bucket_size => $bucket_capacity);
$bucketizer->add_items(map { $_->{id} => $_->{weight} } @fit_items);
my @buckets = $bucketizer->buckets();

# Handle oversized items: assign to dedicated buckets (or split if allowed)
foreach my $item (@oversized) {
    # Calculate how many buckets are needed for this item
    my $num_buckets = int($item->{weight} / $bucket_capacity);
    $num_buckets += 1 if ($item->{weight} % $bucket_capacity != 0);
    
    # Add each required bucket (label parts if splitting is okay)
    for my $i (1..$num_buckets) {
        push @buckets, [ "$item->{id} (Part $i)" ];
        # If splitting isn't allowed, just add the full item to a single bucket (adjust capacity if possible)
        # push @buckets, [ $item->{id} ];
    }
}

This way, you don’t lose track of item E—you’ll either split it across 3 buckets (since 3*30=90 covers 88) or assign it to a single dedicated bucket if your system allows variable-sized buckets.

2. Switch to Perl Modules with Built-In Oversized Item Support #

There are other Perl modules designed to handle edge cases like oversized items:

• Algorithm::BinPacking: This module includes options to configure how oversized items are handled. You can set a policy where items larger than the bin size are placed in their own bin instead of being excluded.
• Algorithm::Knapsack: While it’s focused on the classic knapsack problem, you can extend it with custom checks to catch oversized items first, then run the standard packing on the rest.

3. Use a Modified Bin Packing Algorithm #

If you’re open to implementing custom logic, consider variants of the bin packing algorithm that explicitly handle oversized items:

• First-Fit Decreasing (FFD) with Oversized Handling: Sort items by weight descending, then for each item:
  • If it fits in an existing bucket, place it there.
  • If it’s oversized, create a new bucket (or multiple buckets) to accommodate it.
• Variable-Sized Buckets: If your use case permits, adjust buckets to fit oversized items directly instead of forcing a fixed capacity. This works well if you’re not constrained to uniform bucket sizes.

The best approach depends on your specific needs: if items are indivisible, go with dedicated buckets for oversized items; if splitting is allowed, calculate the number of buckets needed.

内容的提问来源于stack exchange，提问作者rooger