Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #define N 101
- #define INF 100005
- using namespace std;
- int n, m;
- int a[N], d[N][INF];
- int main() {
- cin >> n >> m;
- for (int i = 1; i <= n; i++)
- cin >> a[i];
- for (int i = 0; i <= m; i++) {
- for (int j = 1; j <= n; j++) {
- d[j][i] = INF;
- }
- }
- sort(a + 1, a + 1 + n);
- d[1][0] = 0;
- d[1][a[1]] = 1;
- for (int i = 2; i <= n; i++) {
- for (int j = 0; j <= m; j++) {
- if (j - a[i] >= 0) {
- d[i][j] = min(d[i - 1][j], d[i - 1][j - a[i]] + 1);
- }
- else d[i][j] = d[i - 1][j];
- }
- }
- d[n][m] != INF ? cout << d[n][m] : cout << 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement