# Solution bài Cái túi 4
- Bài này dùng quy hoạch động đảo nhãn với ý tưởng là bài cái túi thông thường
## Ý tưởng 1: Dp hai chiều
- Gọi dp[i][j] là xét tới vật thứ i có giá trị là j
- Khi này ta có công thức:
- Chọn: dp[i + 1][j + v[i]] = min(dp[i + 1][j + v[i]], dp[i][j] + w[i])
- Không chọn: dp[i + 1][j] = min(dp[i + 1][j], dp[i][j])
- Lưu ý: bộ nhớ để lưu mảng dp là rất lớn (1GB) nên ta sẽ tiến tới cải tiến dp
## Ý tưởng 2: Cải tiến dp
- Gọi dp[j] là khối lượng nhỏ nhất có giá trị là j
- Dựa vào ý tưởng 1, ta có thể cải tiến như sau
- dp[j] = min(dp[j], dp[j - v[i]] + w[i])
- Lúc này ta sẽ chỉ cần dp[505 * 505]
## Code mẫu bài này
```
#include <bits/stdc++.h>
/* Author: Dang Minh Sang. 12A2 - Ngo Quyen High School. Code created at 07h22 - Tue, 19-11-2024*/
#define ll long long
#define FASTER ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define pii pair <int, int>
#define pll pair <ll, ll>
#define vi vector <int>
#define fi first
#define se second
#define rsz resize
#define mpair make_pair
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define mem(a, i) memset((a), (i), sizeof(a))
#define FOR(i, a, b) for (int (i) = (a); i <= (b); i++)
#define REP(i, a, b) for (int (i) = (a); i >= (b); i--)
#define File(a) freopen(a ".INP", "r", stdin); freopen(a".OUT", "w", stdout);
using namespace std;
#define endl '\n'
const int N = 505;
const int MOD = 1e9 + 7;
const int INF = 1e9 + 7;
int n, s;
ll dp[N * N];
int w[N], v[N];
int ans = 0;
void solve()
{
dp[0] = 0;
FOR(i, 1, n)
{
REP(j, N * N - 1, v[i])
{
if (dp[j - v[i]] + w[i] <= s)
{
dp[j] = min(dp[j], dp[j - v[i]] + w[i]);
ans = max(ans, j);
}
}
}
cout << ans;
}
int main()
{
mem(dp, INF);
FASTER;
cin >> n >> s;
FOR (i, 1, n)
cin >> w[i] >> v[i];
solve();
}
```
MINHSANGNOAC
Created at
0 likes