- 论坛徽章:
- 1
|
本帖最后由 ttcn_cu 于 2011-03-26 06:54 编辑
回复 29# py
不递归
- #!perl -w
- use strict;
- my @original=(
- [100=>11111111111],
- [20=>11111111111],
- [5=>11111]
- ); #原始存的货币数目
- my $input=2175;
- my $count=0;
- my @backup=map {
- [
- $_->[0],
- $a=int($input/$_->[0])<$_->[1]?int($input/$_->[0]):$_->[1],
- $_->[0]*$a
- ]
- } @original; #优化备份
- my @worker = map { [$_->[0],$_->[1]]} @backup;
- $_->[2]=$_->[0]*$_->[1] for @worker;
- BIG:
- while (1){
- $count++;
- my $sum=0;
- for (0..$#worker-1){
- $sum+=$worker[$_]->[2];
- }
- $sum+=$worker[$#worker]->[0]*$worker[$#worker]->[1];
- my $delta=$sum-$input;
- if ($delta==0){
- print "$sum = ";
- print join " + ", map { "$_->[0] * $_->[1]" } grep {$_->[1] } @worker;
- last BIG;
- }
- for my $idx (reverse 0..$#worker){
- next if $worker[$idx]->[1]==0;
- if ($idx!=$#worker){
- $worker[$idx]->[1]--;
- }
- else{ #最小面额使用贪婪
- $worker[$idx]->[1] =
- ($delta <= $worker[$idx]->[0]||int($delta/$worker[$idx]->[0])>$worker[$idx]->[1])
- ?
- 0
- :
- $worker[$idx]->[1] - int($delta/$worker[$idx]->[0]);
- }
- $worker[$idx]->[2] = $worker[$idx]->[0] * $worker[$idx]->[1];
- @worker[($idx+1)..$#worker] = map { [$_->[0],$_->[1],$_->[2]] } @backup[($idx+1)..$#worker];
- next BIG;
- }
- print "not found";
- last BIG;
- }
- print "\nloop count=$count";
复制代码 |
|