All possible combinations of two lists

[Ed W.]

I am trying to write a script to list all the possible combinations of gift
certificate denominations for a given order total. For example, if a person
has $25.00 to spend, they can purchase 1 $25.00 certificate, 2 $10.00
certificates and 1 $5.00 certificate, etc.

The code I have so far is listed below. I am struggling with all of the
possible combinations. I think I have to recurs through each of the items,
but I can't figure out how to do that. Can anyone post some relevant
sections in the docs, or other examples similar to this?

use Data:ump qw(dump);
use strict;

my @denoms = sort { $a <=> $b } qw(25 10 5 50);
my @totals = qw(25 40);

my %results;

# Loop through each value
foreach my $total_value (@totals) {

my %temp;
my $remainder = $total_value;
foreach my $denom (@denoms) {

# Check each denomination and see if it is evenly divisible.
if ( ($total_value % $denom) == 0 ) {
push(@{$results{$total_value}},
{ $denom => ($total_value/$denom) });
}

# Add one denomination to a local count
if ($total_value > $denom) {
$temp{$denom} += 1;
$remainder -= $denom;
}
}
push(@{$results{$total_value}}, \%temp) if ($remainder == 0);
}
print dump(\%results);


Thanks
-Ed W.

 

[Jürgen Exner]

I am trying to write a script to list all the possible combinations
of gift certificate denominations for a given order total. For
example, if a person has $25.00 to spend, they can purchase 1 $25.00
certificate, 2 $10.00 certificates and 1 $5.00 certificate, etc.

The code I have so far is listed below. I am struggling with all of
the possible combinations. I think I have to recurs through each of
the items, but I can't figure out how to do that. Can anyone post
some relevant sections in the docs, or other examples similar to this?

Your problem has little to do with Perl and you won't find anything in the
doc's that is relevant to your problem.

But it is a very famous example in computer science for an NP complete
problem.
Try to do some research on the knapsack problem. There are _many_ algorithm
and ideas in computer literature about it.
You should be able to adapt those solutions with almost no modification for
your specific problem.

jue