背包重量 > 最大尺寸

Question

我目前的查询结果如下

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

人数 = 体重

A 15
B 23
C 10
D 8

E 88

use Algorithm::Bucketizer;

my $b = Algorithm::Bucketizer->new( bucketsize => 30);
for my $i (1..10) {
    $b->add_item($i, 30+$i);
}

for my $bucket ($b->buckets()) {
    for my $item ($bucket->items()) {
        print "Bucket ", $bucket->serial(), ": Item $item\n";
    }
    print "\n";
}

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

使用这个模块，我正在应用背包算法来尝试将物品的重量分配给桶

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

问题是当重量大于我正在搜索的尺寸时，该重量被排除在外。

示例：

桶大小 => 30

E 88 这将被排除

是否有其他算法可以解决这种情况？或者有没有办法修改这个不排除比尺码大的重量？

是否可以将其调整为这样工作？

如果重量 > 大小，则只用该重量填充一个桶

Answer 1

我看不出你卡在什么地方了。您只需在现有算法中添加一个 pre-processing 步骤。你对重量进行一次传递。当您找到一个 >= bucketsize 时，只需将那个重量装满一个桶即可。然后从问题集中删除那个重量和水桶并照常继续。

在上面的示例中，您将从

开始

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

继续您通常的解决方案，在 return 之后附加 88 公斤的桶。

Answer 2

对于超过存储桶大小的任何项目，只需传递存储桶大小而不是实际大小。

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();

背包重量 > 最大尺寸

knapsack weight > max size

algorithm

perl

knapsack-problem