スポンサーサイト

--.--.-- --:--  スポンサー広告

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

| - | - | ↑ページトップ |




カードの総和

2007.09.28 10:27  パソコン甲子園 2007

パソコン甲子園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 }

スポンサーサイト

テーマ : プログラミング - ジャンル : コンピュータ

| コメント(0) | トラックバック(0) | ↑ページトップ |

この記事へのコメント

コメントを書く


管理人にのみ表示

↑ページトップ

この記事へのトラックバック

この記事にトラックバックする(FC2ブログユーザー)

↑ページトップ

上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。