Problem description

There's a magic pocket , The total volume is 40, You can make it out of this pocket
Some articles , The total volume of these items must be 40.  John Now there are n（1≤n ≤ 20） Items you want , Each item
The volumes of are a1,a2……an.John You can choose one of these items
some , If the total volume of the selected object is 40, So take advantage of this amazing
pocket ,John You can get these things . Now the problem is ,John Yes
How many different ways to choose items .
input
The first line of input is a positive integer n (1 <= n <= 20), Representing different items
Number . Next n That's ok , One per line 1 reach 40 Positive integer between , part
Give a1,a2……an Value .

output

Output the number of different ways to choose items

sample input

3
20
20
20

sample output

3

The solution of enumeration ：

Enumerate whether each item is selected or not , common 2
20 Species condition

Obviously not .
Recursive solution
#include <iostream> using namespace std; int a[30]; int N; int Ways(int w ,int
k) { // before k Choose some of the items , Volume in volume w Practice Number if( w == 0 ) return 1; if( k <= 0 ) return 0;
return Ways(w, k -1 ) + Ways(w - a[k], k -1 ); } int main() { cin >> N; for( int
i= 1;i <= N; ++ i ) cin >> a[i]; cout << Ways(40,N); return 0; }
Dynamic gauge solution
#include <iostream> using namespace std; int a[30]; int N; int Ways[50][40];
//Ways[i][j] Express former j Make volume out of items i Number of methods int main() { cin >> N; memset(Ways,0,sizeof(Ways)
); for( int i = 1;i <= N; ++ i ) { cin >> a[i]; Ways[0][i] = 1; } Ways[0][0] = 1
; for( int w = 1 ; w <= 40; ++ w ) { for( int k = 1; k <= N; ++ k ) { Ways[w][k]
= Ways[w][k-1]; if( w-a[k] >= 0) Ways[w][k] += Ways[w-a[k]][k-1]; } } cout <<
Ways[40][N]; return 0; }

Technology
Daily Recommendation
views 26
views 2