# 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
#∈clude<bitsstdc++.h>⋅Author:DangM∈hSang.12A2-NgoQuyenHighSch∞l.Codecreatedat07h22-Tue,19-11-2024⋅#def∈elllonglong#def∈eFASTERiosbase::syncwithstdio(0);c∈.tie(0);cout.tie(0);#def∈eπipair<∫,∫>#def∈epllpair<ll,ll>#def∈evi→→r<∫>#def∈efifirst#def∈esesecond#def∈erszresize#def∈empairmakepair#def∈eall(x)beg∈(x),end(x)#def∈esz(x)(∫)(x).size()#def∈emem(a,i)memset((a),(i),sizeof(a))#def∈eFOR(i,a,b)for(∫(i)=(a);i≤(b);i++)#def∈eREP(i,a,b)for(∫(i)=(a);i≥(b);i--)#def∈eFi≤(a)eopen(a.INP,r,std∈);eopen(a.OUT,w,stdout);usingnamespacestd;#def∈eendl′n′const∫N=505;const∫MOD=1e9+7;const∫INF=1e9+7;∫n,s;lldp[N⋅N];∫w[N],v[N];∫ans=0;voolve(){dp[0]=0;FOR(i,1,n){REP(j,N⋅N-1,v[i]){if