Processing math: 33%
Solutions of Knapsack 4 - MarisaOJ: Marisa Online Judge

Solutions of Knapsack 4

Select solution language

Write solution here.


User Avatar MINHSANGNOAC    Created at    4 likes

# 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:DangMhSang.12A2-NgoQuyenHighSchl.Codecreatedat07h22-Tue,19-11-2024#defelllonglong#defeFASTERiosbase::syncwithstdio(0);c.tie(0);cout.tie(0);#defeπipair<,>#defepllpair<ll,ll>#defevir<>#defefifirst#defesesecond#deferszresize#defempairmakepair#defeall(x)beg(x),end(x)#defesz(x)()(x).size()#defemem(a,i)memset((a),(i),sizeof(a))#defeFOR(i,a,b)for((i)=(a);i(b);i++)#defeREP(i,a,b)for((i)=(a);i(b);i--)#defeFi(a)eopen(a.INP,r,std);eopen(a.OUT,w,stdout);usingnamespacestd;#defeendlnconstN=505;constMOD=1e9+7;constINF=1e9+7;n,s;lldp[NN];w[N],v[N];ans=0;voolve(){dp[0]=0;FOR(i,1,n){REP(j,NN-1,v[i]){if