---
# System prepended metadata

title: Ngu

---

# **Bài 1**: Cái Túi

```cpp
 #include <bits/stdc++.h>
 
 using namespace std;
 
 long long n,t,F[105][200005],W[10005],V[10005];
 
 int main() {
     cin >> n >> t;
     for (int i = 1; i <= n; ++i) cin >> W[i] >> V[i];
     for (int i = 1; i <= n; ++i)
         for (int j = 1; j <= t; ++j)
             if (j >= W[i]) F[i][j] = max(F[i-1][j-W[i]] + V[i],F[i-1][j]);
         else F[i][j] = F[i-1][j];
     cout << F[n][t];
     return 0;
 }
```

# **Bài 2**: Dãy Con Có Tổng Bằng S

```cpp
 #include <bits/stdc++.h>
 
 using namespace std; 
 const int MOD = 1e9+7;
 long long n,s,A[105];
 int F[1005];
 
 int main() {
     memset(F,0,sizeof(F));
     F[0] = 1;
     cin >> n >> s;
     for (int i = 1; i <= n; ++i) cin >> A[i];
     for (int i = 1; i <= n; ++i)
         for (int j = s; j >= A[i]; --j)
             F[j] = (F[j] + F[j-A[i]]) % MOD;
     cout << F[s];
     return 0;
}
```

# **Bài 3**: Chia Kẹo

```cpp
 #include <bits/stdc++.h>
 
 using namespace std;
 
 bool F[100005];
 int n,s = 0,A[105];
 int main() {
     memset(F,false,sizeof(F));
     F[0] = true;
     cin >> n;
      for (int i = 1; i <= n; ++i ) {
         cin >> A[i];
         s += A[i];
     }
     for (int i = 1; i <= n; ++i)
         for (int j = s; j >= A[i]; --j)
             if (F[j - A[i]])
                 F[j] = true;
     for (int i = s/2; i >= 1; i--) if (F[i]) {
         cout << s - (i*2);
         exit(0);
     }
     return 0;
 }
```

# **Bài 4**: Tích Lớn Nhất

```cpp
 #include <bits/stdc++.h>
 
 using namespace std;
 
 bool F[100005];
 int n,s = 0,A[105];
 int main() {
     memset(F,false,sizeof(F));
     F[0] = true;
     cin >> n;
     for (int i = 1; i <= n; ++i ) {
         cin >> A[i];
         s += A[i];
     }
     for (int i = 1; i <= n; ++i)
         for (int j = s; j >= A[i]; --j)
             if (F[j - A[i]])
                 F[j] = true;
     for (int i = s/2; i >= 1; i--) if (F[i]) {
         cout << i*(s-i);
         exit(0);
     }
     return 0;
 }
```


