#2.Bài Toán Cái Túi Quy Hoạch Động| Bài Toán Xếp Balo ( 01 Knapsack)

[@Tuano-et5el]

ở phần Hướng dẫn thì tại dp[3][5], dp[4][5],dp[3][6] phải bằng 7 chứ

[@enderfly_ytb135]

22:15 sửa rồi

[@Skidjcjxj]

giải thích chi tiết cho những ai chưa hiểu qhd theo ý hiểu của mình dp[i][j] ở đây sẽ là giá trị tối ưu của cái túi tính đến đồ vật thứ i và khối lương cái túi là j, trong công thức dp[i][j]=dp[i-1][j] ở đây nghĩa là ta sẽ cập nhập cái túi hiện tại bằng việc lấy kết quả từ cái túi ở đồ vật đằng trước đã chọn tức là độ vật thứ i-1 còn công thức dp[i][j]=max(dp[i][j],dp[i-1][j-w[i]]+v[i]) tức là cái túi hiện tại sẽ so sánh với cái túi khi ta bỏ đi một khối lương là w[i[ để lần về lời là cái túi có khối lương j-w[i] đã giải được và sẽ lấy kết quả ở ô đã giải được đó cộng thêm giá trị v[i] và sẽ so sánh 2 kết quả là giá trị cái túi hiện tại và sau khi thêm 1 đồ vật vào và nó sẽ lấy max của 1 trong 2 giá trị, giả trị nào tối ưu hơn thì sẽ lấy và cứ làm như v đến hết kq sẽ nằm ở ô cuối cùng của bàng phương án là dp[n][S] cách làm này là sử dụng mảng 2 chiều để lưu phương án,ae muốn ngắn hơn thì cố nghĩ cách sử dụng mảng 1 chiều

[@topnewapps6169]

Con tim e đã tan chảy khi được nghe bài giảng của a mỗi ngày❤

[@vuhoangbach189]

thôi

[@lds8455]

anh giảng rất dễ hiểu ạ, em xem nhiều bên rồi thấy anh giảng chậm tận tâm

[@28tech_]

Cảm ơn em :D

[@NamTranVan-dx9gn]

xem thỉ hiểu mà sao tìm được công thức hay vậy ta +1 respect hay vô cùng mn nên xem để biết nhé

[@28tech_]

@@NamTranVan-dx9gn những bài kinh điển thì thường phải xem hướng dẫn nhé bạn, khi đủ kinh nghiệm r thì việc tìm cthuc sẽ dễ hơn

[@ucanh6473]

Có cách nào hiểu rõ hơn về cái CT được không anh,em hiểu hết chỉ là e ko hiểu bản chất của cái công thức ạ

[@MinhAnh-gd8hy]

yêu anh nhiều lắm luôn á🥰🥰 anh ra nhiều video nữa đi anh

[@28tech_]

uh a đang chuyển nơi làm việc nên chưa làm được nhiều. Con gái thì chấp nhận nhé, con trai thì anh né trước.

[@MinhAnh-gd8hy]

@@28tech_ hihhiihi anh ra tiếp nhá anh🤗🤗 em chuẩn bị thi icpc asia 2022 nên cần học tập ở anh nhiều ạ😇😇

[@QuyVietBui]

còn thi năm sau không bạn

[@quangdungle731]

Dạ anh ơi cho em hỏi ở phút 14:38 ở 2 cột 5 và 6 thì mình phải điền vào số 7 mới đúng phải không anh?

[@nguyenhuy6734]

tui ms code xg cx ra 7 clm

[@QUANGHUYNGHIEM-t4s]

cuoi video a loc co sua r a bn

[@itnhalam]

anh mà ra khóa quy hoạch động thì em sẽ là người đăng kí đầu tiên :D

[@28tech_]

Hehe cảm ơn em

[@06.chungvanduya13]

Mong anh làm thêm nhiều video về phần này nx nha a💪💪

[@28tech_]

Ok thank em đã ủng hộ, chia sẻ cho a đi

[@HienNguyen-op4mo]

Bài giảng hay quá trời hay anh ơi, học cuốn mà dễ hiểu

[@28tech_]

Cảm ơn em

[@MinhKhoi-m5j]

không có những video hướng dẫn này chắc em không tự nghĩ ra được lời giải luôn. đưa nó ra thực tế thì chẳng bao giờ có thể nghĩ là đang có một cái túi chứa 5kg mà lại giả sử cho 1kg, 2kg,...,5kg được🥲

[@vietvuong9830]

Mình hiểu db[i-1][j-w[i]] có ý nghĩa là chỗ túi còn thừa sau khi cho đồ vật i đó vào còn nhét thêm được cái gì không các bạn ạ!

[@KhaiHoan-ov3bh]

nó có nghĩa là giá trị lớn nhất có thể chôm được nếu xét cái ba lô khi chưa bỏ đồ vật i vào, j - w[i] có nghĩa đang xét tới trường hợp balo nặng tối đa khi chưa bỏ đồ vật i vào, bỏ đồ vật i vào thì cái balo nó nặng thêm w[i] lên, thì khối lượng balo lúc đó sẽ là j

[@kiethuynh641]

Cảm ơn bạn, đọc cmt của bạn ngẫm một hồi mình cũng hiểu ra :))

[@aristia6746]

ra thêm video quy hoạch động đi anh ơiiiiiii

[@tinhNguyen-jx4pp]

bài giảng hay lắm ạ

[@28tech_]

😌🤩🤩🤩 thank em

[@ABCb33]

tuyệt vời quá anh ơi

[@oanlekieu5453]

ban đầu ko hiểu công thức, nghe giảng ko hiểu muốn đập bể bàn luôn=))) nhưng mà hiểu rồi thì thấy cũng hay. QHD giống rễ cây ha, cứ nhánh nào mọc được thì mọc

[@CongNguyen-fi5cd]

này quy hoạch động à bn , mk tưởng mà exhuasted(vét cạn) chứ nhỉ

[@Nuc-ny4bz]

Dạ anh ơi nếu phải cout những cái tui đã chọn thì duyệt lại thế nào ạ!

[@nguyenquocbao1198]

*ANH CHO EM HỎI MINH HỌA THUẬT TOÁN CÓ PHẢI LẬP BẢNG, TRA BẢNG K Ạ?*

[@ytnt6829]

Anh giảng hay quá ạ e đã like share và sub cho anh ròi

[@28tech_]

😆😆

[@TungNguyen-gq5ms]

làm sao để bt hàng nào dc chọn v anh

[@khanhhuyen8630]

Tại sao mình có thể khai báo kích thước mảng là giá trị nhập vào như `int w[n+1]` ạ?

[@ThanhKim-lb7vf]

Sau khi mình cin>>n thì nó tính luôn n+1 cho kích thước mảng w nhé bạn( tuy nhiên có 1 số phần mềm lại yêu cầu mảng là hằng số)

[@bldouyin4145]

thề là e xem 4 lần cái video của anh mới hiểu được nó hđ như nào đấy :))

[@28tech_]

Haha ok em, kiên trì quá

[@thanhtungtrinh8021]

Anh chsu thích i là gì với j là gì được không ạ ?

[@Ha-bi9kk]

hay quá ạ, em đợi series QHD này mãi :( mong a làm DP bitmask sớm ạ.

[@28tech_]

Làm loại này có mấy người xem đâu em, kén lắm :D, mấy series của anh đã kén rồi. hehe.

[@Ha-bi9kk]

@@28tech_ :( em luôn ủng hộ a ạ

[@28tech_]

@@Ha-bi9kk

[@hieuang9353]

@@28tech_đến h là gần 50k ng xem là đỉnh r a ơi

[@BaoNguyên-u7q2t]

Hay quá a

[@thanhbinhnguyen5943]

Quá hay luôn anh ơi ~~~

[@28tech_]

Cảm ơn em

[@yordle6_613]

cho em hỏi là nếu j >= w[i] thì chắc gì khi thêm đồ vật thứ i vào thì ( j + w[i] )

[@minhnguyen-ky4zu]

j ở đây là giá trị lớn nhất mà cái túi có thể chứa, vậy khi j >= w[i] thì tức là nó đủ lớn để cho đồ vật thứ i vào, nếu cho được đồ vật thứ i vào rồi thì mình phải cập nhập giá trị của dp[i][j] đó theo công thức thôi, chứ lấy j + w[i] làm gì cậu

[@roxkingreus9373]

có dạng nào làm theo kiểu 2 cái túi ko anh kiểu lấy 2 cái cùng lúc ấy

[@hungLab]

Hay quá anh ơi😍😍

[@TKenz-xe9ny]

vậy làm sao để in ra số đồ vật mang đi và tổng trọng lượng ủa chúng v a

[@punchone1760]

anh ơi em có cách làm bài này khác, nhưng mà dễ hiểu lắm!!

[@khaihoannguyen9446]

có thì show cho ae đi ông, để tham khảo với

[@traninhtheanh6138]

Từ tận đáy lòng em mong anh có thể làm nhiều hơn 😢

[@28tech_]

Có chia sẻ video chưa thế -_-

[@traninhtheanh6138]

@@28tech_ Có nhaaaaaaa

[@traninhtheanh6138]

@@28tech_ Mà anh lộc. Bữa anh có nói mai mốt có khóa c++ sau thì học chứ khóa lúc đó hơn 60 người rồi, đông nên anh không nhận. H e thấy có 1 khóa c++ vào tháng 5. Anh có thể giúp em một cơ hội để được học k ạ. Em biết ơn anh nhiều lắm!

[@dswgith.4639]

Hay quá ạ!!! Mong a làm nhiều về QHD và tham lam nữa ạ😝😝😝

[@28tech_]

Tham lam 😆😆😆

[@nguyenvanthang7277]

a ơi nếu muốn in ra chọn những đồ vật theo kiểu (0-1) nào thì qhd đc ko ạ hay phải dùng nhánh cận a

[@quyetleduy6440]

Dùng QHD vs nhánh cận có phải lúc nào cũng cho ra cùng kq không anh, hay có một thuật toán sẽ chính xác hơn ạ

[@tunghoang2853]

hay 👍👍👍

[@Lunguyen08]

Bài toán cái túi chọn nhiều lần thì sao anh

[@quangnhat6164]

em sắp thi tuyển bổ sung, anh có thể ra video luyện giải các đề được không ạ.... big fan;3333

[@TungNguyen-gq5ms]

mấy dòng trong hàm main từ cin.tie(nullptr) trở về trước để làm gì v anh

[@28tech_]

đồng bộ cin cout vs print scanf để tăng tốc độ đọc ghi nhé e.

[@ThinhNguyen-ii2of]

Anh cho em hỏi ạ, trong clip ở phần chạy tay trong excel, khi xét tới dp[3][5] và dp[3][6] thì giá trị tại 2 ô đấy phải là 7 chứ phải k ạ? Hay là em nhầm ở đâu ạ? Mong a giải đáp giúp e ạ!

[@28tech_]

Chắc a nhầm đó em :D

[@ThinhNguyen-ii2of]

@@28tech_ dạ vâng em cảm ơn ạ^^

[@langtri3835]

mn oi co tip lm may bai quy hoach dong ntn ko a?

[@ucminhpham8316]

truy vet thi sao a

[@giakhanhle2098]

nếu chọn nhiều lần thì công thức vẫn thế à anh

[@BaoTran-kw6qu]

làm sao để biết chọn món nào vậy anh

[@haonhat8478]

j >= a[i] với j là trọng lượng túi đang xét, a[i] là trọng lượng đồ vật

[@AnTran-zt9xn]

@@haonhat8478 chắc ý bạn ấy là làm sao để biết cái túi nào đc chọn sau khi code xong như trên

[@sss-rq1mc]

sao bài này không dùng mảng 1 chiều mà phải sử dụng mảng 2 chiều nhỉ

[@gianglo123]

cho e xin link bai

[@nguyenhoa5409]

Anh có dự định làm cả chia và trị với tham lam ko anh

[@28tech_]

Chưa biết em ạ, thời gian tới xem kênh phát triển tốt thì anh triển khai.

[@traninhtheanh6138]

@@28tech_ Em nghĩ anh nên dành thời gian để ra về các chủ đề thuật toán đó. Em nghĩ đây là một mảng chủ đề mà ít người chỉ dạy và giải bài tập như anh. Nếu anh làm thì sẽ có tiềm năng phát triển lớn vì không có quá nhiều người làm trong khi số người muốn học và tìm hiểu lại nhiều

[@28tech_]

@@traninhtheanh6138 không đúng đâu em ạ, anh làm a biết mà.

[@traninhtheanh6138]

@@28tech_ Vậy hả anh. Tại em thấy các bạn tự học qua tài liệu trên mạng rồi làm bài tập trên web vs tài liệu là chính. Để tìm kiếm một video chỉ giảng bài tập thì rất hiếm. Bản thân em cũng như vậy nên rất cần một kênh ytb như anh

[@ken2ker495]

a ơi e chưa hiểu cái đoạn d[i][j] = max(d[i][j],d[i-1][j-w[j]]+v[i]) , a giải thích kĩ cho e chỗ d[i-1][j-w[j]]+v[i] đi ạ , e chưa hiểu tại sao phải làm v ạ

[@caohuunghia9444]

ez

[@lnkmobile9504]

e vẫn không hiểu tại sao lại có công thức đó vậy ạ =(((

[@edmmusic9791]

mình muốn biết vật được chọn là những vật nào thì phải code sao hả anh

[@nguyenthiennhan4376]

viết them hàm trace ngược lại nha bạn

[@redfoxbvn]

viết chữ main xong ra nguyên đoạn code làm sao làm đc v ạ?

[@28tech_]

Này a dùng snippet

[@minhkienngo1483]

đỉnh quá a iu

[@28tech_]

😍😍😍 nhớ chia sẻ cho a

[@TKenz-xe9ny]

i và j là gì thế a

[@tanluongminh7562]

cho em hỏi bài toán balo theo dạng 0-1 là mỗi đồ vật có thể lấy hoặc ko lấy và có thể lấy nhiều lần đúng ko a ?

[@taiphanvan2403]

quy hoạch động chỉ áp dụng cho bài toán mà mỗi đồ vật chỉ đc lấy 1 lần thôi phải k anh ? Nếu mà mỗi đồ vật được lấy nhiều lần thì dùng kĩ thuật nhánh cận phải k anh?

[@ProxyTvr]

vẫn dùng đc, nhân k vào công thức thôi

[@blan39212]

a ưi ngay vị trí dp[3][5] vs vị trí dp[3][6] thì có giá trị là 7 đk ạ :(( em cũng không chắc nên hỏi mong anh trả lời giúp ạ

[@thanetnt6269]

đúng rồi bạn thứ tự là 0 3 3 6 6 7 7 mà kết quả cuối vẫn đúng bạn ạ

[@blan39212]

@@thanetnt6269 dạ vâng mình cảm ơn

[@superlmaoehehe]

xem 4 tiếng mới hiểu :))

[@plee0577]

tuyệt :>>

[@28tech_]

😍😍😍😍

[@105-12TrươngVănKhôi]

thuật toán này hình như sai phải không int w[] = {5, 4, 7, 1,3}; int v[] = {7, 6, 10, 2,3}; mình cho như thế này mà nó ra chỉ có 13 đáng lẻ 15 mới đúng chớ

[@105-12TrươngVănKhôi]

phải thêm 0 ở phía trước mảng nữa nó mới trả 15 có ai biết vì sao không ạ

[@hvttnvn]

Không hiểu sao k ai hỏi, Dp[i][j] = max(dp[i][j].... , Đã biết dp[i][j] là cái gì đâu mà ông cho làm phần tử của max như đúng rồi.

[@28tech_]

@@hvttnvn bạn hiểu hàm memset ko?

[@vuongtien9700]

Hi 😁

[@28tech_]

Fan cứng hehe. :v

[@vuongtien9700]

@@28tech_ em muốn lập trình game android phải học gì ạ hiện em học xong c++ rồi mà em ko biết nên học gì thêm

[@thanetnt6269]

@@vuongtien9700 vote c# + unity

[@adabseff5848]

khai sánggg

[@MinhLe-fw3kz]

Anh ơi, sắp tới anh có làm video về html, css không ạ

[@28tech_]

anh ko làm web nên a code cái này xấu lắm hehe.

[@phamnguyenquoctho1578]

nộp vnoj đúng dc 3 test :))

[@28tech_]

Nếu nộp bài thì bạn có thể tham khảo code này. #include using namespace std; using ll = long long; ll F[101][100005]; int main(){ int n, W; cin >> n >> W; int w[n + 1], v[n + 1]; for(int i = 1; i > w[i] >> v[i]; } for(int i = 1; i

[@phamnguyenquoctho1578]

v phải làm sao để mình đúng được full test z ad

[@28tech_]

@@phamnguyenquoctho1578 Bạn gửi code mình xem thử, có thể bạn code sai :D

[@phamnguyenquoctho1578]

@@28tech_ đúng dc 7 test hà ad

[@phamnguyenquoctho1578]

@@28tech_ #include using namespace std; long long n,m,w[100]={},v[100]={},a[41][41]={}; int main(){ cin>>n>>m; for(int i=1;i>w[i]>>v[i]; for(int i=1;i

[@annguyenthien2963]

cho em xin code với anh ơi :((

[@28tech_]

Mấy dòng mà còn lười code thế này 😿😿😿