背包重量>最大尺寸

Question

我目前有一个查询，结果如下

A，B，C，D，E =项目

数=重量

1. A 15
2. B 23
3. C 10
4. D 8
5. E 88 使用算法：：Bucketizer；my $b =算法:Bucketizer>new(桶大小为=> 30)；用于我的$i (1..10) { $b->add_ Item ($i，30+$i)；}用于my $bucket ($b->桶子()){ for my $item ($桶->Item()){打印“桶"，$桶->串行()，"：Item $item\n"；}打印"\n"；}

http://search.cpan.org/~mschilli/Algorithm-Bucketizer-0.13/Bucketizer.pm

使用此模块，我将应用背包算法尝试将项目的权重分配到桶中。

my $bucketizer = Algorithm::Bucketizer->new(bucketsize => $size);

问题是，当重量更大时，我正在寻找的那个重量被排除在外。

示例：

桶大小=> 30

1. E 88将被排除在外

还有另一种算法可以解决这种情况吗？或者，是否有一种方法来修改这个不排除大于大小的重量？

能不能把它调整成这样？

如果重量>大小，那么只将这个重量装满一个桶。

Answer 1

只需传递桶大小，而不是任何项目的实际大小高于桶大小。

use Algorithm::Bucketizer qw( );
use List::Util            qw( min );

my @items = ...;
my $bucket_size = 30;

my $bzer = Algorithm::Bucketizer->new( bucketsize => $bucket_size );
for my $i (0..$#items) {
    $bzer->add_item( $i => min($items[$i], $bucket_size) );
}

my @bucketed_items = map { [ $bucket->items() ] } $bzer->buckets();

或者，因为您知道过大的值将占用整个桶，过滤掉它们并将它们添加到结果中。

use Algorithm::Bucketizer qw( );

my @items = ...;
my $bucket_size = 30;

my $bzer = Algorithm::Bucketizer->new( bucketsize => $bucket_size );
my @bucketed_items;
for my $i (0..$#items) {
    if ($items[$i] >= $bucket_size) {
        push @bucketed_items, [ $i ];
    } else {
        $bzer->add_item( $i => $items[$i] );
    }
}

push @bucketed_items, map { [ $bucket->items() ] } $bzer->buckets();

Answer 2

我不知道你被困在哪里了。您只需在现有的算法中添加一个预处理步骤。你一次就通过了重量。当您找到一个>= bucketsize时，只需将该重量装满一个桶即可。然后从问题集中移除这个重量和桶，像往常一样继续。

在上面的例子中，您应该从

bucket[0] = 88
weights = [15, 23, 10, 8]

继续你通常的解决方案，在你回来后附加88公斤的水桶。