poj 1837 Balance

题目链接：http://poj.org/problem?id=1837

    用DP求解，相当与01背包。起初依然是没有想到具体的思路，看了下解题报告后发现与01背包如此接近。

    

    从此题开始进入DP模式... 

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std ;
int dp[20][15010], C[25], G[25] ;
int main(){
    int c, g, i, j, k ;
    while(~scanf("%d%d", &c, &g)){
        for(i=1; i<=c; i++)
            cin >> C[i] ;
        for(i=1; i<=g; i++)
            cin >> G[i] ;
        memset(dp, 0, sizeof(dp)) ;
        dp[0][7500] = 1 ;
        for(i=1; i<=g; i++){
            for(j=1; j<=15000; j++){
                if(dp[i-1][j])
                    for(k=1; k<=c; k++)
                        dp[i][j+G[i]*C[k]] += dp[i-1][j] ;
            }
        }
        cout << dp[g][7500] << endl ;
    }
    return 0 ;

}