Итак, вам нужно заполнить заказ пакетами так, чтобы общая цена была максимальной? Это известно как проблема рюкзака . В этой статье Википедии вы найдете несколько решений, написанных на Python.
Точнее, вам нужно решение для неограниченной задачи о ранце, в отличие от популярной проблемы с ранцем 0/1 (где каждый предмет может быть упакован только один раз). Вот рабочий код из Розетты :
from itertools import product
NAME, SIZE, VALUE = range(3)
items = (
# NAME, SIZE, VALUE
('A', 3, 5),
('B', 5, 9),
('C', 9, 16))
capacity = 13
def knapsack_unbounded_enumeration(items, C):
# find max of any one item
max1 = [int(C / item[SIZE]) for item in items]
itemsizes = [item[SIZE] for item in items]
itemvalues = [item[VALUE] for item in items]
# def totvalue(itemscount, =itemsizes, itemvalues=itemvalues, C=C):
def totvalue(itemscount):
# nonlocal itemsizes, itemvalues, C
totsize = sum(n * size for n, size in zip(itemscount, itemsizes))
totval = sum(n * val for n, val in zip(itemscount, itemvalues))
return (totval, -totsize) if totsize <= C else (-1, 0)
# Try all combinations of bounty items from 0 up to max1
bagged = max(product(*[range(n + 1) for n in max1]), key=totvalue)
numbagged = sum(bagged)
value, size = totvalue(bagged)
size = -size
# convert to (iten, count) pairs) in name order
bagged = ['%dx%d' % (n, items[i][SIZE]) for i, n in enumerate(bagged) if n]
return value, size, numbagged, bagged
if __name__ == '__main__':
value, size, numbagged, bagged = knapsack_unbounded_enumeration(items, capacity)
print(value)
print(bagged)
Вывод:
23
['1x3', '2x5']
Имейте в виду, что это NP-сложная проблема, поэтому она взорвется когда вы вводите несколько больших значений:)
Вы не должны возвращать ссылку на массив, если это несовместимо с остальной частью Вашего интерфейса. Если все остальное, что Вы работаете со списками возвратов вместо ссылок, не является нечетной уткой, которая заставляет других программистов помнить исключение.
Если у Вас нет больших списков, это - действительно проблема микрооптимизации. Необходимо быть настолько удачливыми, если это - узкое место в программе.
Насколько сложность идет, различие между ссылкой и списком до сих пор снижается в масштабе сложности, что у Вас есть большие проблемы, если Ваши программисты борются с этим. Сложные алгоритмы и рабочие процессы сложны, но это - просто синтаксис.
Сказав все относительно это, я склонен заставлять все возвратить ссылки и сделать интерфейсы согласовывающимися с этим.
Нет. Кроме действительно "возвращают $result"; для ясности.
Я не забываю тестировать эффективность тех, и разница в производительности была минимальна для небольших массивов. Для больших массивов, возвращая ссылку был путь быстрее.
Это - действительно вещь удобства для маленького результата. Скорее сделайте это:
($foo,$bar) = barbaz();
Или возврат ссылки:
$foobar = barbaz();
$foobar->[0]; # $foo
$foobar->[1]; # $bar
Другой способ возвратить ссылку:
($foo,$bar) = @{barbaz()};
Как правило, после того как Вы решаете, который способ пойти, просто придерживайтесь его для Вас модуль, так как это делает его путающий для переключения от одного метода до следующего.
Я обычно возвращаю ссылки массива для списков подобных вещей и массив, когда ответ состоит из двух - четырех различных элементов. Больше, чем это, я делаю хеш, с тех пор не, вся вызывающая сторона будет заботиться обо всех элементах ответа.
Я скопирую соответствующую часть своего ответа от другого вопроса здесь.
Часто пропущенное второе соображение является интерфейсом. Как возвращенный массив собирается использоваться? Это важно, потому что целое разыменование массива довольно ужасно в Perl. Например:
for my $info (@{ getInfo($some, $args) }) {
...
}
Это ужасно. Это намного лучше.
for my $info ( getInfo($some, $args) ) {
...
}
Это также предоставляет себя отображению и захвату.
my @info = grep { ... } getInfo($some, $args);
Но возврат массива касательно может быть удобным, если Вы собираетесь выбрать отдельные элементы:
my $address = getInfo($some, $args)->[2];
Это более просто, чем:
my $address = (getInfo($some, $args))[2];
Или:
my @info = getInfo($some, $args);
my $address = $info[2];
Но в той точке, необходимо подвергнуть сомнению, является ли @info действительно списком или хешем.
my $address = getInfo($some, $args)->{address};
В отличие от массивов по сравнению с судьями массива, существует мало причины принять решение возвратиться, хеш по хешу касательно судей Hash позволяют удобную стенографию, как код выше. И противоположность массивов по сравнению с судьями, это делает случай итератора более простым, или по крайней мере избегает переменной посредника.
for my $key (keys %{some_func_that_returns_a_hash_ref}) {
...
}
То, что Вы не должны делать, имеют getInfo()
возвратите массив касательно в скалярном контексте и массиве в контексте списка. Это запутывает традиционное использование скалярного контекста как длина массива, которая удивит пользователя.
Я хотел бы добавить, что, заставляя все последовательно сделать X хорошее эмпирическое правило, это не первостепенной важности в разработке хорошего интерфейса. Немного зайдите слишком далеко с ним, и можно легко пробиться с боями другие более важные проблемы.
Наконец, я включу свой собственный модуль, Метод:: Подписи, потому что это предлагает компромисс для передачи в ссылках на массив, не имея необходимость использовать массив касательно синтаксиса.
use Method::Signatures;
method foo(\@args) {
print "@args"; # @args is not a copy
push @args, 42; # this alters the caller array
}
my @nums = (1,2,3);
Class->foo(\@nums); # prints 1 2 3
print "@nums"; # prints 1 2 3 42
Это сделано через волшебство Данных:: Псевдоним.
Если массив создается в функции нет никакой причины возвратить массив; просто возвратите ссылку, так как вызывающей стороне гарантируют это только будет одна копия ее (она была просто создана).
Если функция рассматривает ряд глобальных массивов и возвращает одного из них, то приемлемо возвратить ссылку, если вызывающая сторона не изменит его. Если вызывающая сторона могла бы изменить массив, и это не желаемо, то функция должна возвратить копию.
Это действительно исключительно проблема Perl. В Java Вы всегда возвращаете ссылку, и функция препятствует тому, чтобы массив был изменен (если это - Ваша цель) путем завершения и массива и данных, которые это содержит. В Python возвращаются ссылки и нет никакого способа препятствовать тому, чтобы они были изменены; если это важно, ссылка на копию возвращается вместо этого.
Я просто хочу прокомментировать идею о неуклюжем синтаксисе обработки ссылки на массив в противоположность списку. Как brian упомянутый, Вы действительно не должны делать этого, если остальная часть системы использует списки. Это - ненужная оптимизация в большинстве случаев.
Однако если это не так, и Вы свободны создать свой собственный стиль, затем одна вещь, которая может сделать кодирование менее вонючим, использует автополе. autobox
повороты SCALAR
, ARRAY
и HASH
(а также другие) в "пакеты", такие, что можно кодировать:
my ( $name, $number ) = $obj->get_arrayref()->items( 0, 1 );
вместо немного более неуклюжего:
my ( $name, $number ) = @{ $obj->get_arrayref() };
путем кодирования чего-то вроде этого:
sub ARRAY::slice {
my $arr_ref = shift;
my $length = @$arr_ref;
my @subs = map { abs($_) < $length ? $_ : $_ < 0 ? 0 : $#$arr_ref } @_;
given ( scalar @subs ) {
when ( 0 ) { return $arr_ref; }
when ( 2 ) { return [ @{$arr_ref}[ $subs[0]..$subs[1] ] ]; }
default { return [ @{$arr_ref}[ @subs ] ]; }
}
return $arr_ref; # should not get here.
}
sub ARRAY::items { return @{ &ARRAY::slice }; }
Следует иметь в виду это autobox
требует, чтобы Вы реализовали все поведения, которые Вы хотите от них. $arr_ref->pop()
не работает, пока Вы не определяете sub ARRAY::pop
если Вы не используете автополе:: Ядро
Существует ли причина, я не должен делать этого, даже для маленьких результатов?
Нет perl-определенной причины, означая, что это корректно и эффективно возвратить ссылку на локальный массив. Единственный недостаток - то, что люди, которые вызывают Вашу функцию, должны иметь дело с возвращенным массивом касательно, и элементы доступа со стрелкой ->
или разыменуйте и т.д. Так, это немного более неприятно для вызывающей стороны.
Я не думаю, что необходимо чувствовать себя принужденными только к использованию одного или двух методов. Необходимо однако сохранить это последовательным для каждого модуля или набора модулей.
Вот некоторые примеры для размышляния:
sub test1{
my @arr;
return @arr;
}
sub test2{
my @arr;
return @arr if wantarray;
return \@arr;
}
sub test3{
my %hash;
return %hash;
}
sub test4{
my %hash;
return %hash if wantarray;
return \%hash;
}
sub test5{
my %hash;
return $hash{ qw'one two three' } if wantarray;
return \%hash;
}
{
package test;
use Devel::Caller qw'called_as_method';
sub test6{
my $out;
if( wantarray ){
$out = 'list';
}else{
$out = 'scalar';
}
$out = "call in $out context";
if( called_as_method ){
$out = "method $out";
}else{
$out = "simple function $out";
}
return $out;
}
}
Я вижу возможно использование многих из них в будущем проекте, но некоторые из них довольно бессмысленны.
Возврат массива приносит некоторую хорошую пользу:
my @foo = get_array(); # Get list and assign to array.
my $foo = get_array(); # Get magnitude of list.
my ($f1, $f2) = get_array(); # Get first two members of list.
my ($f3,$f6) = (get_array())[3,6]; # Get specific members of the list.
sub get_array {
my @array = 0..9;
return @array;
}
Если Вы судьи возвращаемого массива, необходимо будет записать несколько нижних индексов, чтобы сделать ту же работу. Кроме того, пустой массив возвращает false в булевом контексте, но пустой массив касательно не делает.
if ( get_array() ) {
do_stuff();
}
Если Вы судьи возвращаемого массива, то необходимо сделать:
if ( @{ get_array_ref() } ) {
do_stuff();
}
Кроме того, если get_array_ref () не удается возвратиться касательно, сказать вместо этого и значение undef, у Вас есть программа, останавливающая катастрофический отказ. Одно из следующего поможет:
if ( @{ get_array() || [] } ) {
do_stuff();
}
if ( eval{ @{get_array()} } ) {
do_stuff();
}
Таким образом, если преимущества скорости необходимы или если Вам нужен массив касательно (возможно, Вы хотите позволить непосредственное управление элементом набора объекта - фу, но иногда это должно произойти), возвратите массив касательно Иначе, я нахожу преимущества стандартных массивов стоящими сохранения.
Обновление: действительно важно помнить, что то, что Вы возвращаете из стандартной программы, является не всегда массивом или списком. То, что Вы возвращаете, - то, что следует return
, или результат последней операции. Ваше возвращаемое значение будет оценено в контексте. Большую часть времени все будет прекрасно, но иногда можно получить неожиданное поведение.
sub foo {
return $_[0]..$_[1];
}
my $a = foo(9,20);
my @a = foo(9,20);
print "$a\n";
print "@a\n";
Сравните:
sub foo {
my @foo = ($_[0]..$_[1]);
return @foo;
}
my $a = foo(9,20);
my @a = foo(9,20);
print "$a\n";
print "@a\n";
Так, когда Вы говорите, "возвращают массив" быть уверенным, что Вы действительно имеете в виду, "возвращают массив". Знайте о том, что Вы возвращаете из своих стандартных программ.
Когда Вы используетесь для использования кода так же первый отрывок в Mathieu Longtin ответ, необходимо написать ужасный код как второй отрывок, или это не настолько лучше кодирует:
my ($foo,$bar) = @{barbaz()};
Я думаю, что это - самый большой недостаток при возврате ссылки вместо массива. Если я хочу небольшое количество возврата значений другого вида. Я привык к возвращаемому массиву и присваиваюсь непосредственно к переменным (как используется сделать в Python, например).
my ($status, $result) = do_something();
if ($status eq 'OK') {
...
Если сумма значений является большим и различным видом, я используюсь для возврата хеша касательно (лучше для рефакторинга)
my ($status, $data, $foo, $bar, $baz) =
@{do_something()}{qw(status data foo bar baz)};
if ($status eq 'OK') {
...
Если возвращаемые значения являются тем же видом, чем возврат массива или массива касательно спорен в зависимости от суммы.
Я не уверен, если возврат ссылки более эффективен в этом случае; т.е. Perl копирует данные, возвращенные подпрограммами?
В целом, если Ваш массив создается полностью в подпрограмме затем нет никакой очевидной проблемы с возвратом ссылки, потому что иначе массив был бы отброшен так или иначе. Однако, если ссылка также передается в другое место прежде, чем возвратить его, у Вас может быть две копии той же ссылки, и это может быть изменено в одном месте, но, как не ожидать, в другом месте.
Поскольку никто не упоминал о wantarray
, я: -)
Я считаю хорошей практикой позволить вызывающей стороне решить, в каком контексте она хочет получить результат. Например, в приведенном ниже коде вы запрашиваете у Perl контекст, в котором была вызвана подпрограмма, и решаете, что вернуть.
sub get_things {
my @things;
... # populate things
return wantarray ? @things : \@things;
}
Затем
for my $thing ( get_things() ) {
...
}
и
my @things = get_things();
работают правильно из-за контекста списка, и:
my $things = get_things();
вернет ссылка на массив.
Для получения дополнительной информации о wantarray
вы можете проверить perldoc -f wantarray
.
Edit: Я недооценил один из первых ответы, в которых упоминается wantarray
, но я думаю, что этот ответ все еще действителен, потому что он делает его немного понятнее.
Важное упущение в приведенных выше ответах: не возвращайте ссылки на личные данные!
Например:
package MyClass;
sub new {
my($class) = @_;
bless { _things => [] } => $class;
}
sub add_things {
my $self = shift;
push @{ $self->{_things} } => @_;
}
sub things {
my($self) = @_;
$self->{_things}; # NO!
}
Да, пользователи могут заглядывать прямо под капот с объектами Perl, реализованными таким образом, но не облегчают пользователям возможность непреднамеренно выстрелить себе в ногу , например, ,
my $obj = MyClass->new;
$obj->add_things(1 .. 3);
...;
my $things = $obj->things;
my $first = shift @$things;
Лучше было бы вернуть (возможно, глубокую) копию ваших личных данных, как в
sub things {
my($self) = @_;
@{ $self->{_things} };
}