常规01背包模型问题
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast,no-stack-protector")
#include <bits/stdc++.h>
const int N = 1e4 + 10 ;
int f[N] , a[105] ;
int n , m ;
int main()
{
std::ios::sync_with_stdio(false) ;
std::cin.tie(nullptr) ;
#ifdef LOCAL
freopen("D:\\Codes\\in.txt" , "r" , stdin) ;
freopen("D:\\Codes\\out.txt" , "w" , stdout) ;
#endif
std::cin >> n >> m ;
for(int i = 1 ; i <= n ; ++ i)
std::cin >> a[i] ;
f[0] = 1 ;
for(int i = 1 ; i <= n ; ++ i)
for(int j = m ; j >= a[i] ; -- j)
f[j] += f[j - a[i]] ;
std::cout << f[m] << '\n' ;
return 0 ;
}
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast,no-stack-protector")
#include <bits/stdc++.h>
const int N = 1e4 + 10 ;
int f[105][N] , a[105] ;
int n , m ;
int main()
{
std::ios::sync_with_stdio(false) ;
std::cin.tie(nullptr) ;
#ifdef LOCAL
freopen("D:\\Codes\\in.txt" , "r" , stdin) ;
freopen("D:\\Codes\\out.txt" , "w" , stdout) ;
#endif
std::cin >> n >> m ;
for(int i = 1 ; i <= n ; ++ i)
std::cin >> a[i] ;
f[0][0] = 1 ;
for(int i = 1 ; i <= n ; ++ i)
for(int j = 0 ; j <= m ; ++ j)
{
f[i][j] = f[i - 1][j] ;
if ( j >= a[i] ) f[i][j] += f[i - 1][j - a[i]] ;
}
std::cout << f[n][m] << '\n' ;
return 0 ;
}