Problem 0154 : Sum of Cards

Sum of Cards
http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=0154

• 問題概要

書いてある数字の違う数種類のカードが与えられて、そのカードの合計で数字を作る。
枚数は任意である。
与えられた数字を作る組み合わせは何通りあるか。

• 解法

DFSで全部つくった。
最初DPでしようとしていたが断念。
DFSの方が簡潔にできることに気づいた。

• ソース

#include<iostream>
#include<algorithm>

#define MAX 1001

using namespace std;
int v[7], num[7], n;  
int t[MAX];

void dfs(int now, int sum){
  if( now == n){
    t[sum]++;
    return;
  }
  for(int i=0; i<=num[now]; i++){
    int tmp = sum + v[now] * i;
    if(tmp >= MAX)return;
    dfs(now + 1, tmp);
  }
}
main(){


  while(cin >> n){
    if(n == 0)break;
    

    for(int i=0; i<n; i++){
      cin >> v[i] >> num[i];
    }

    fill(t, t + MAX, 0);

    dfs(0, 0);
    
    cin >> n;

    for(int i=0; i<n; i++){
      int tmp;
      cin >> tmp;
       cout << t[tmp] << endl;
    }
  }
}