カードの総和

パソコン甲子園2007予選問題

問題07 カードの総和

概要

m （m < 8）種類（各種類のカードは複数(<11)存在する）のカードの集合から数枚カードを選んで、カードに書かれた数字の合計が n になるような組み合わせ数を出力せよ。

解法

再帰関数によって、全てのカードの組み合わせについての数字の合計を試します。
再帰関数内では、k 種類目のカードを 0 枚から amout[k] (k 種類目のカードの枚数)枚選んで、
k + 1 種類目のカードを選ぶ処理に移ります。
この過程で、選んだカードにかかれた数字の合計 v を計算していき、v が n と等しくなったとき、
カウンターを増やします。

サンプルプログラム

001 #include<iostream>
002 using namespace std;
003 #define MAX 7
004 
005 int m, n, counter;
006 int value[MAX], amount[MAX];
007 
008 void recursive( int k, int v ){
009     if ( v == n ) {
010         counter++; return;
011     } else if ( v > n || k >= m ) return;
012     
013     for ( int a = 0; a <= amount[k]; a++ ){
014         recursive( k + 1, v + value[k]*a );
015     }
016 }
017 
018 int main(){
019     while( cin >> m, m ){
020         for ( int i = 0; i < m; i++ ){
021             cin >> value[i] >> amount[i];
022         }
023         int g; cin >> g;
024         for ( int i = 0; i < g; i++ ){
025             cin >> n;
026             counter = 0;
027             recursive(0, 0);
028             cout << counter << endl;
029         }
030     }
031     return 0;
032 }