AOJ : 0154 - Sum of Cards
問題概要
http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=0154&lang=jp
日本語の問題文があるので省略です
アルゴリズム
動的計画法で解きました。
dp[i][j] には、カード[0]〜カード[i] までを使って、合計点を j にするための組み合わせ数が記憶されます。
ここでのアルゴリズムは、3重ループになっていますが、カードの種類数と枚数が非常に少ないので、計算時間は全くかかりません。
詳しくは、プログラムを見てください。
プログラム
#include <stdio.h> #include <string.h> int main(void){ int i,j,k; int n,m,val,a[7],b[7]; int dp[8][1001]; while(scanf("%d",&n), n){ for(i=0;i<n;i++){ scanf("%d%d",&a[i],&b[i]); } memset(dp,0,sizeof(dp)); dp[0][0] = 1; //カードの番号 for(i=0;i<n;i++){ //合計点 for(j=0;j<=1000;j++){ //i番目のカードを何枚使用するか for(k=0;k<=b[i];k++){ if(j+a[i]*k>1000) continue; //1001以上はいらないので無視 dp[i+1][j+a[i]*k] += dp[i][j]; } } } scanf("%d",&m); while(m--){ scanf("%d",&val); printf("%d\n",dp[n][val]); } } return 0; }