(完全背包求方案数)

题目描述

给你一个n种面值的货币系统，求组成面值为m的货币有多少种方案。

输入格式

第一行，包含两个整数n和m。

接下来n行，每行包含一个整数，表示一种货币的面值。

输出格式

共一行，包含一个整数，表示方案数。

数据范围

n≤15,m≤3000

输入样例：

3 10
1
2
5

输出样例：

10

样例

#include <iostream>

using namespace std;

typedef long long LL ;

const int M = 3010 , N = 20 ;

int v[N] ;
//LL f[N][M]; //f[i][j]:选择前i个物品价值恰好为j
LL f[M] ;

int main()
{
    int n , m ;
    cin >> n >> m;

    for (int i = 1 ; i <= n ; i ++) cin >> v[i] ;

    //f[0][0] = 1;
    //二维 O(n^3)
    // for (int i = 1 ; i <= n ; i ++)
    //     for (int j = 0 ; j <= m ; j ++)
    //         for (int k = 0 ; k * v[i] <= j ; k ++)
    //         {
    //             f[i][j] += f[i - 1][j - k * v[i]];
    //         }

    //二维 O(n^2) f[i][j] = f[i - 1][j] + f[i][j - v[i]] (== f[i - 1][j - k * v[i]])
    // for (int i = 1 ; i <= n ; i ++)
    //     for (int j = 0 ; j <= m ; j ++)
    //     {
    //         f[i][j] += f[i - 1][j] ; //
    //         if (v[i] <= j) f[i][j] += f[i][j - v[i]];
    //     }
    //cout << f[n][m] << endl;

    //一维
    f[0] = 1 ;
    for (int i = 1 ; i <= n ; i ++)
        for (int j = v[i] ; j <= m ; j ++)
            f[j] += f[j - v[i]];
    cout << f[m] << endl;        
    return 0 ;
}