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
©2019-2020 Toolsou All rights reserved,
Java Swing JList: List box components Accurate mobile phone number capture , Big data of operators The difference between memory overflow and memory leak , Causes and Solutions Website mobile phone number capture method stay Vue Use in Web Worker3 species Python data structure ,13 Creation methods , This is the conclusion , Great ! What's the difference in server prices ? Basic definition and use of function ‘ To be continued SQL Server Database Glossary Chrome OS, For programmers and Windows What does it mean ? Internet Marketing