Method number problem for solving sum of numbers (knapsack problem)

Title Description ：

Problem description : Given a n An array of positive integers a And an integer sum, Find selection array a The sum of the middle part of the figure is sum Number of alternatives . If the subscript of a number is different between the two selection schemes , It is considered to be a different scheme .

Input description : Input two lines , The first 1 Two positive integers n(1≤n≤1000)、sum(1≤sum≤1000), The first 2 Behavior n A positive integer a[i](32 An integer ), Space off .

Output description : Output the number of solutions .

sample input ：

5 15

5 5 10 2 3

sample output ：

4

Ideas ： The classical knapsack problem is to find the number of solutions , Definition f[i][j] For the past i Number selected , And for j Number of schemes . Then the state transfer equation is

No second choice i Number ：f[i][j] += f[i - 1][j]

Choose the first i Number ：f[i][j] += f[i - 1][j - w[i]

Here we use rolling array optimization , See code for details ：

#include <iostream>

using namespace std;

typedef long long LL;

const int N = 1010;

int n, m, w[N], f[N];

int main()
{
	cin >> n >> m;
	for(int i = 1; i <= n; i ++ ) cin >> w[i];
	
	f[0] = 1;
	
	for(int i = 1; i <= n; i ++ )
	for(int j = m; j >= w[i]; j -- )
	f[j] += f[j - w[i]];
	
	cout << f[m] << endl;
	return 0;
}