アルゴリズムの問題いろいろ

  • 合計金額になるすべてのお金の組み合わせを計算する。

例:10ドル、5ドル、1ドルを組み合わせて123ドルになるのは何通り?

use strict;

sub f{
	my( $amount, @curs ) = @_;
	my $cur = shift @curs;
	my $total;
	
	return 0 unless $cur;

	if( @curs == 0 ) {
		return 1 unless $amount % $cur;
		return 0 if $amount % $cur;
	}

	for( my $i=0; $i<=$amount/$cur; $i++ ){
		$total += f( $amount - ($cur*$i), @curs );
	}
	
	return $total;
	
}

print f( @ARGV );
perl amount.pl 123 10 5 1
169
  • C++で書く場合
#include <stdio.h>
#include <stdlib.h>

int subTotal(int total, int cur[], int start, int end){
  if(total==0) return 1;
  int pat=0;
  if((end-start)>0){
    for(int i=0; i*cur[start]<=total; i++){
      pat += subTotal( total-i*cur[start], cur, start+1, end );
    }
  }
  else {
    if( total % cur[start] == 0 ) pat++;
  }
  return pat;
}

int main(int args, char* argv[]){
  int *cur = new int[args-1];
  for(int i=0; i<args-2; i++)
    cur[i] = atoi( argv[i+2] );
  int result = subTotal( atoi(argv[1]), cur, 0, args-3 );
  printf("%d", result);
  delete cur;
  return 0;
}
# a.out 1234 100 50 20 10 5 1
6764940