yeah, first "*" never tries 0. (update: hmm, no, it does try, for 10.. then I don't know why..) But if you actually specify the max number of matches

my $choices = join "\n   ",
   map { "(  .{$_} (?{ my \%r = \%{\$^R}; \$r{$_}++; +{ \%r } })  ){0,
+".(int($amount/$_))."}" }
                   @bills;
[download]

it works fine:

12:28pm /home/Ivancho/bin> probichka.pl 20
(?x-ism:
   ^
   (?{ +{} })
   (  .{1} (?{ my %r = %{$^R}; $r{1}++; +{ %r } })  ){0,20}
   (  .{5} (?{ my %r = %{$^R}; $r{5}++; +{ %r } })  ){0,4}
   (  .{10} (?{ my %r = %{$^R}; $r{10}++; +{ %r } })  ){0,2}
   (  .{20} (?{ my %r = %{$^R}; $r{20}++; +{ %r } })  ){0,1}
   (  .{50} (?{ my %r = %{$^R}; $r{50}++; +{ %r } })  ){0,0}
   (  .{100} (?{ my %r = %{$^R}; $r{100}++; +{ %r } })  ){0,0}
   $
   (?{ push(@matches, $^R) })
   (?!)
)

$VAR1 = [
          {
            '1' => 20
          },
          {
            '1' => 15,
            '5' => 1
          },
          {
            '1' => 10,
            '5' => 2
          },
          {
            '1' => 10,
            '10' => 1
          },
          {
            '1' => 5,
            '5' => 3
          },
          {
            '1' => 5,
            '10' => 1,
            '5' => 1
          },
          {
            '5' => 4
          },
          {
            '10' => 1,
            '5' => 2
          },
          {
            '10' => 2
          },
          {
            '20' => 1
          }
        ];
[download]