1 // source code of submission 1098949, Zhongshan University Online Judge System
2 /*
3 2014 sicily
4 完全背包问题
5 把硬币看成一件一件来的物品 ， 数量不限 ，面值看成其cost ，
6 填充进cost总和为总面值V,
7 代码编写风格参考背包九讲
8 */
9 #include <stdio.h>
10 #include <memory.h>
11 int V , dp[301];
12 int value[9];
13
14
15 void ZeroOnePack( int cost ) // 完全背包调用函数 v 从 cost到 V ；
16 {
17 for ( int v = cost ; v <= V ; v++)
18 dp[ v ] += dp[ v - cost ];
19 }
20 int main()
21 {
22 int num ; //货币种类
23 scanf("%d%d" , &V , &num);
24 for ( int i = 1 ; i <= num ; i++)
25 scanf("%d" , value + i ) ;
26 memset( dp , 0 , sizeof( dp) );
27 dp[0] = 1 ;
28 for ( int i = 1 ; i <= num ; i ++ )
29 ZeroOnePack( value[i] ) ;
30 printf("%d\n" , dp[V] );
31 return 0 ;
32 }