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
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
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
@@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!
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 ạ!
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🥲
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
@@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_ 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
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?
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 ạ
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ớ
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
![#25 [C++]. Giải Thích Cách Hàm Đệ Quy Hoạt Động | Kỹ Thuật Đệ Quy Trong C++](http://i.ytimg.com/vi/eQ3VpTtc9lE/mqdefault.jpg)
ở phần Hướng dẫn thì tại dp[3][5], dp[4][5],dp[3][6] phải bằng 7 chứ
22:15 sửa rồi
Con tim e đã tan chảy khi được nghe bài giảng của a mỗi ngày❤
thôi
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
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
Cảm ơn em :D
yêu anh nhiều lắm luôn á🥰🥰
anh ra nhiều video nữa đi anh
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.
@@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 ạ😇😇
còn thi năm sau không bạn
anh mà ra khóa quy hoạch động thì em sẽ là người đăng kí đầu tiên :D
Hehe cảm ơn em
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?
tui ms code xg cx ra 7 clm
cuoi video a loc co sua r a bn
Bài giảng hay quá trời hay anh ơi, học cuốn mà dễ hiểu
Cảm ơn em
Mong anh làm thêm nhiều video về phần này nx nha a💪💪
Ok thank em đã ủng hộ, chia sẻ cho a đi
bài giảng hay lắm ạ
😌🤩🤩🤩 thank em
tuyệt vời quá anh ơi
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é
@@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
Anh giảng hay quá ạ
e đã like share và sub cho anh ròi
😆😆
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 ạ
Quá hay luôn anh ơi ~~~
Cảm ơn em
Hay quá anh ơi😍😍
Hay quá a
hay quá ạ, em đợi series QHD này mãi :( mong a làm DP bitmask sớm ạ.
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.
@@28tech_ :( em luôn ủng hộ a ạ
@@Ha-bi9kk
@@28tech_đến h là gần 50k ng xem là đỉnh r a ơi
hay 👍👍👍
Hay quá ạ!!! Mong a làm nhiều về QHD và tham lam nữa ạ😝😝😝
Tham lam 😆😆😆
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] )
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
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
này quy hoạch động à bn , mk tưởng mà exhuasted(vét cạn) chứ nhỉ
hay!
làm sao để bt hàng nào dc chọn v anh
Từ tận đáy lòng em mong anh có thể làm nhiều hơn 😢
Có chia sẻ video chưa thế -_-
@@28tech_ Có nhaaaaaaa
@@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!
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]` ạ?
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ố)
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 ạ!
Chắc a nhầm đó em :D
@@28tech_ dạ vâng em cảm ơn ạ^^
Dạ anh ơi nếu phải cout những cái tui đã chọn thì duyệt lại thế nào ạ!
thề là e xem 4 lần cái video của anh mới hiểu được nó hđ như nào đấy :))
Haha ok em, kiên trì quá
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🥲
ra thêm video quy hoạch động đi anh ơiiiiiii
*ANH CHO EM HỎI MINH HỌA THUẬT TOÁN CÓ PHẢI LẬP BẢNG, TRA BẢNG K Ạ?*
mấy dòng trong hàm main từ cin.tie(nullptr) trở về trước để làm gì v anh
đồng bộ cin cout vs print scanf để tăng tốc độ đọc ghi nhé e.
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
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 ạ!
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
Cảm ơn bạn, đọc cmt của bạn ngẫm một hồi mình cũng hiểu ra :))
mọi người cho e hỏi nếu mà 1 vật được chọn nhiều lần thì làm sao ạ
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
Anh chsu thích i là gì với j là gì được không ạ ?
đỉnh quá a iu
😍😍😍 nhớ chia sẻ cho a
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 ạ
anh ơi em có cách làm bài này khác, nhưng mà dễ hiểu lắm!!
có thì show cho ae đi ông, để tham khảo với
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
làm sao để biết chọn món nào vậy anh
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
@@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
vậy làm sao để in ra số đồ vật mang đi và tổng trọng lượng ủa chúng v a
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 ?
nếu chọn nhiều lần thì công thức vẫn thế à anh
truy vet thi sao a
mn oi co tip lm may bai quy hoach dong ntn ko a?
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
viết them hàm trace ngược lại nha bạn
Anh có dự định làm cả chia và trị với tham lam ko anh
Chưa biết em ạ, thời gian tới xem kênh phát triển tốt thì anh triển khai.
@@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
@@traninhtheanh6138 không đúng đâu em ạ, anh làm a biết mà.
@@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
cho e xin link bai
Bài toán cái túi chọn nhiều lần thì sao anh
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?
vẫn dùng đc, nhân k vào công thức thôi
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 ạ
ez
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ỉ
tuyệt :>>
😍😍😍😍
viết chữ main xong ra nguyên đoạn code làm sao làm đc v ạ?
Này a dùng snippet
Hi 😁
Fan cứng hehe. :v
@@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
@@vuongtien9700 vote c# + unity
i và j là gì thế a
e vẫn không hiểu tại sao lại có công thức đó vậy ạ =(((
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 ạ
đú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 ạ
@@thanetnt6269 dạ vâng mình cảm ơn
Anh ơi, sắp tới anh có làm video về html, css không ạ
anh ko làm web nên a code cái này xấu lắm hehe.
xem 4 tiếng mới hiểu :))
khai sánggg
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ớ
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 ạ
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.
@@hvttnvn bạn hiểu hàm memset ko?
Ngáo
cho em xin code với anh ơi :((
Mấy dòng mà còn lười code thế này 😿😿😿
nộp vnoj đúng dc 3 test :))
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
v phải làm sao để mình đúng được full test z ad
@@phamnguyenquoctho1578 Bạn gửi code mình xem thử, có thể bạn code sai :D
@@28tech_ đúng dc 7 test hà ad
@@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