Bạn Việt Nguyễn Phong có hỏi: "ở phần bài toán cái túi em không hiểu sao U = V - xk*gk, vì nếu U là khổi lượng còn lại sau khi đã chọn các sản phẩm từ 1 đến k-1. khi thêm 1 sản phẩm nữa thì rõ ràng khổi lượng còn lại của balo ph..." Tôi giải thích như sau: Khi tạo bảng thì thực hiện từ trên xuống dưới (k từ 1 đến n) còn khi tra bảng để xác định kết quả thì lấy từ dưới lên (k từ n đến 1). Do đó giả sử khối lượng còn lại của ba lô là V, sau khi lấy xk đồ vật loại k thì khối lượng còn lại của ba lô sẽ là U= V-xk*gk, và khối lượng U này của ba lô để dành cho việc chọn các loại đồ vật từ 1 đến k-1.
Câu 2: Giả sử có n công việc và n thợ. Chi phí trả cho người thợ i để làm công việc j là Ci,j. Mỗi công việc chỉ do một thợ thực hiện và ngược lại. Tìm cách thuê thợ làm việc sao cho tổng chi phí là nhỏ nhất. Sử dụng kỹ thuật thiết kế để viết giải thuật giải quyết bài toán trên. Câu 3: Cho một lưới hình vuông cấp n, mỗi ô được gán với một số tự nhiên. Tại một ô có thể di chuyển đến ô khác theo các hường: xuống dưới, sang phải ( ô cạnh kề phía dưới và bên phải). Tìm đường đi từ ô đầu tiên (1,1) đến ô (n,n) sao cho tổng các ô đi qua là nhỏ nhất. Thiết kế giải thuật để giải quyết bài toán này. Thầy hướng dẫn giải 2 câu này giúp e với ạ! Em cảm ơn thầy nhiều ạ
Trong kênh của tôi đã có giải bài phân công lao động và tam giác số bằng nhiều kỹ thuật khác nhau. Em tham khảo tại đây nhé th-cam.com/channels/8HHhH_Pa6_l-eaieKzjlSw.html
@@cautrucdulieuvagiaithuat-n6504 dạ ko, em năm sau có nguyện vong chuyên tin LHP ạ, mà có ít thầy dạy và cung cấp kiến thức cho bọn em về phần chuyên tin ấy ạ nên em hơi còn mơ hồ. Chỗ em lại ko có cho thi hsg tin nên đành tự học ạ. Nếu có thể em mong thầy có thể làm nhiều video về phần đó ạ e cám ơn thầy
Thầy có thể giúp em hai câu này không ạ Câu 2: Giả sử có n công việc và n thợ. Chi phí trả cho người thợ i để làm công việc j là Ci,j. Mỗi công việc chỉ do một thợ thực hiện và ngược lại. Tìm cách thuê thợ làm việc sao cho tổng chi phí là nhỏ nhất. Sử dụng kỹ thuật thiết kế để viết giải thuật giải quyết bài toán trên. Câu 3: Cho một lưới hình vuông cấp n, mỗi ô được gán với một số tự nhiên. Tại một ô có thể di chuyển đến ô khác theo các hường: xuống dưới, sang phải ( ô cạnh kề phía dưới và bên phải). Tìm đường đi từ ô đầu tiên (1,1) đến ô (n,n) sao cho tổng các ô đi qua là nhỏ nhất. Thiết kế giải thuật để giải quyết bài toán này.
Em tham khảo các video clip có trong kênh của tôi Câu 2 là bài toán Phân công lao động, giải bằng tham ăn hoặc nhánh cận Câu 3 tương tự bài tam giác số, cũng có 2,3 cách giải Tham khảo tại: th-cam.com/channels/8HHhH_Pa6_l-eaieKzjlSw.html
Theo lệnh chọn FMax đã trình bày: if(F[k-1][V-xk*(int)dsdv[k].TL]+xk*dsdv[k].GT>FMax){ FMax=F[k-1][V-xk*(int)dsdv[k].TL]+xk*dsdv[k].GT; XMax= xk; } thì nếu có nhiều xk làm cho giá trị FMax lớn bằng nhau thì chon xk đầu tiên. Nếu muốn chọn xk sau cùng thì thay dấu > bằng dầu >= trong biểu thức của if.
Giải phương trình T(1)=C1 và T(n)= 2T(n-1)+C2 Ta có T(n)= 2T(n-1)+C2= 2[2T(n-2)+C2]+C2 (vì T(n-1)= 2T(n-2)+C2 => T(n)= 4T(n-2)+3C2= 4[2T(n-3)+C2]+3C2= 8T(n-3)+7C2 = ….2^iT(n-i)+(2^i-1)C2 (1) Quá trình kết thúc khi n-i=1 hay i=n-1 thay vào (1) ta được T(n)= 2^(n-1)T(1) + [2^(n-1)-1]C2= 2^(n-1)C1 + 2^(n-1)C2 - C2= (C1+C2)2^(n-1)-C2= O(2^n)
X[k,V] là số lượng đồ vật thứ k được chọn ứng với trong lượng còn lại của ba lô là V sao cho F[k,V] lớn nhất. Còn xi trong hàm mục tiêu F(n)=x1*v1+x2*v2+...+xn*vn là số lượng đồ vật thứ i được chọn ứng với trọng lượng được cho ban đầu W của ba lô. Mục tiêu chúng ta phải chọn các xi sao cho F(n) lớn nhất. Mà F(n) chính là F[n,W]. Vậy để cho F(n)=F[n,W] lớn nhất thì phải chọn mọi F[k,V] cũng phải lớn nhất (k=1->n, V=0->W). Từ đó ta xây dựng được bảng F và bảng X (tạo bảng). Căn cứ vào bảng X mà ta tìm được phương án (tra bảng) X= (x1, x2, ..., xn)
F(n,v) là tổng giá trị n loại đồ vật dduwwojc chọn, ứng với trọng lượng còn lại của ba lô là v => Tổng giá trị của n lọai đồ vật được chọn, ứng với trọng tải ban đầu của ba lô W là F(X)=F(n,W)
@Cấu trúc Dữ liệu và Giải thuật - Nguyễn Văn Linh ví dụ như là hàm tính tổ hợp c(int n,int k) ạ Nếu chạy bình thường thì sẽ bị tính lại 1 cái nhiều lần (ví dụ như đoạn 7:49 có 2 cái Comb(2,1) ạ) Thì mình tạo thêm một mảng a[n+1][k+1] và đặt tất cả giá trị là -1 Xong r cho thêm lệnh ở ngay đầu tiên của hàm c(n,k) là: Nếu (a[n][k] khác -1) return a[n][k]; Còn nếu không thì tính c(n,k) r gán vào a[n][k] Cách này có áp dụng đc nhiều dạng bài k ạ, hay một số bài thì thời gian của nó chậm hơn rất nhiều so với qhd ạ
@@giyu4103 đây là công thức toán học thôi. Code theo đệ quy thì có độ phức tạp O (2^n), theo quy hoạch động thì O (n^2). Trong video đã trình bày như thế. Nhưng em nói kết hợp giữa đệ quy và lập bảng thì em viết code cụ thể gửi tôi xem
dạ thầy ơi, phút thứ 26:50 em thắc mắc tại sao 'xk' lại thay đổi từ 0 đến 'V/gk'.Lúc này đồ vật thứ 'k' sẽ có trọng lượng là 'V' thì V=xk.gk==>xk=V/gk, mà V chạy từ 0 đến W, vậy thì 'xk' sẽ chạy từ 0 đến W/gk phải không thầy?
xk chạy từ 0 đến W/gk chỉ là các xk ứng với 1 trường hợp trọng tải của ba lô W. Còn xk chạy từ 0 đến V/gk với mọi V từ 0 đến W là xét hết tất cả các trường hợp trọng tải của ba lô V
@@cautrucdulieuvagiaithuat-n6504 em đang cần tài liệu ôn nâng cao các thuật toán của pascal. Để ôn cho mấy em thpt. Thầy có cho em xin. Cám ơn thầy nhiều.
Thầy ơi con đag ôn thi tin, thầy có thể cho con xin một số tài liệu về quy hạch động pascal đc không ạ Mail con là lythuang823@gmail.com Con cảm ơn bài giảng của thầy ạ
![[LeetCode] 4 Bước để giải bài Quy hoạch động (Dynamic Programming ) | Dùng Python Giải House Robber](http://i.ytimg.com/vi/YeKg_-uGD-w/mqdefault.jpg)
![[Học thuật toán cùng TopAlgo] - Quy hoạch động phần 2](/img/n.gif)
Em sinh viên năm 1 đang học hỏi và tìm hiểu các thuật toán, cảm ơn các kiến thức của thầy. Chúc thầy dồi dào sức khỏe ạ
Cảm ơn em, chúc em học giỏi, thành công
Hay quá thầy ơi, xem lại bài giảng của trường mình vẫn dễ hiểu nhất. Chúc thầy nhiều sức khoẻ ạ!
Cảm ơn em, chúc em mạnh khỏe thành công
thầy dạy rất hay, rất dễ hiểu, mong thầy có nhiều sức khỏe ạ !
Cảm ơn em nhiều
Bạn Việt Nguyễn Phong có hỏi: "ở phần bài toán cái túi em không hiểu sao U = V - xk*gk, vì nếu U là khổi lượng còn lại sau khi đã chọn các sản phẩm từ 1 đến k-1. khi thêm 1 sản phẩm nữa thì rõ ràng khổi lượng còn lại của balo ph..."
Tôi giải thích như sau: Khi tạo bảng thì thực hiện từ trên xuống dưới (k từ 1 đến n) còn khi tra bảng để xác định kết quả thì lấy từ dưới lên (k từ n đến 1). Do đó giả sử khối lượng còn lại của ba lô là V, sau khi lấy xk đồ vật loại k thì khối lượng còn lại của ba lô sẽ là U= V-xk*gk, và khối lượng U này của ba lô để dành cho việc chọn các loại đồ vật từ 1 đến k-1.
Thầy giảng hay quá. Em cảm ơn thầy.
@@ThiSiLamTho cảm ơn em đã động viên
Bác giảng dễ hiểu quá ạ. Cháu mong cần cải thiện âm thanh ạ. Vid đã giúp cháu mở rộng kiến thức rồi ạ
Cảm ơn cháu đã động viên, chúc cháu học giỏi thành công
Hi vọng ad ra nhiều video về lập trình nhiều hơn .Thanks you so much
Hay quá thầy ơi! rất cụ thể, đưa ra cả độ phức tạp nên hiểu sâu sắc hơn. Cảm ơn thầy!
Cảm ơn em, mong rằng các video này sẽ giúp em hiểu rõ hơn các bài học, nhờ đó vận dụng được giải quyết các vấn đề thực tiễn
Em cảm ơn thầy nhiều ạ. Series của thầy rất hay.
Chúc thầy có nhiều sức khỏe để giữ lửa đam mê, làm tiếp series này ạ.
Cảm ơn em, chúc em mạnh khỏe hạnh phúc thành công
Bài giảng của thầy rất dễ hiểu ạ. Em cảm ơn thầy
Cảm ơn em đã động viên
Em cảm ơn thầy rất nhiều. Chúc thầy có thật nhiều sức khỏe để ra thêm nhiều Bài giảng mới !
Cảm ơn em, chúc em học giỏi, thành công.
Em cảm ơn thầy nhiều ạ. Bài giảng của thầy rất hay.
Chúc thầy có nhiều sức khỏe!
Thầy dạy hay thật cái này lúc em học ở trường thì như vịt nghe sấm giờ xem lại video của thầy lại hiểu ngay
Cảm ơn em. Em học trường nào?
em cảm ơn thầy, e cũng đọc nhiều tài liệu nhưng vẫn chưa hiểu rõ, video thầy giúp e rất nhiều. Mong thầy có thêm nhiều video algorithm nữa ạ
Cám ơn thầy rất nhiều!
Thầy cảm ơn em nhiều
ông dạy hay quá ạ
Cảm ơn cháu, chúc cháu học giỏi
Cảm ơn thầy, thầy giảng rất dễ hiểu ạ, chúc thầy có nhiều sức khỏe để ra thêm nhiều video nữa ạ.
Cảm ơn em đã động viên, chúc em an toàn trong đại dịch Covid-19
Chúc thầy có nhiều sức khỏe ạ
@@ngocquy5877 cảm ơn em nhiều
Câu 2: Giả sử có n công việc và n thợ. Chi phí trả cho người thợ i để làm công việc j là Ci,j. Mỗi công việc chỉ do một thợ thực hiện và ngược lại. Tìm cách thuê thợ làm việc sao cho tổng chi phí là nhỏ nhất. Sử dụng kỹ thuật thiết kế để viết giải thuật giải quyết bài toán trên.
Câu 3: Cho một lưới hình vuông cấp n, mỗi ô được gán với một số tự nhiên. Tại một ô có thể di chuyển đến ô khác theo các hường: xuống dưới, sang phải ( ô cạnh kề phía dưới và bên phải). Tìm đường đi từ ô đầu tiên (1,1) đến ô (n,n) sao cho tổng các ô đi qua là nhỏ nhất. Thiết kế giải thuật để giải quyết bài toán này.
Thầy hướng dẫn giải 2 câu này giúp e với ạ!
Em cảm ơn thầy nhiều ạ
Trong kênh của tôi đã có giải bài phân công lao động và tam giác số bằng nhiều kỹ thuật khác nhau. Em tham khảo tại đây nhé
th-cam.com/channels/8HHhH_Pa6_l-eaieKzjlSw.html
Cháu chúc thầy nhiều sức khỏe
Cảm ơn cháu nhiều nhé
thầy dạy hay lắm ạ
Cảm ơn em nhiều
Hay quá thầy ơi . Mong thầy Ra nhiều video với an
Em cảm ơn thầy nhiều lắm ạ
Thầy ơi em cám ơn thầy rất nhiều, em mong thầy có thể ra nhiều video về giải thuật ( đặc biệt dành cho hs thi vào 10 chuyên tin ạ). Em cám ơn thầy ạ.
Em dạy chuyên tin à, trường nào vậy?
@@cautrucdulieuvagiaithuat-n6504 dạ ko, em năm sau có nguyện vong chuyên tin LHP ạ, mà có ít thầy dạy và cung cấp kiến thức cho bọn em về phần chuyên tin ấy ạ nên em hơi còn mơ hồ. Chỗ em lại ko có cho thi hsg tin nên đành tự học ạ. Nếu có thể em mong thầy có thể làm nhiều video về phần đó ạ e cám ơn thầy
hay quá xin cảm ơn thầy ạ
Cảm ơn em đã động viên
Thầy có thể giúp em hai câu này không ạ
Câu 2: Giả sử có n công việc và n thợ. Chi phí trả cho người thợ i để làm công việc j là Ci,j. Mỗi công việc chỉ do một thợ thực hiện và ngược lại. Tìm cách thuê thợ làm việc sao cho tổng chi phí là nhỏ nhất. Sử dụng kỹ thuật thiết kế để viết giải thuật giải quyết bài toán trên.
Câu 3: Cho một lưới hình vuông cấp n, mỗi ô được gán với một số tự nhiên. Tại một ô có thể di chuyển đến ô khác theo các hường: xuống dưới, sang phải ( ô cạnh kề phía dưới và bên phải). Tìm đường đi từ ô đầu tiên (1,1) đến ô (n,n) sao cho tổng các ô đi qua là nhỏ nhất. Thiết kế giải thuật để giải quyết bài toán này.
Em tham khảo các video clip có trong kênh của tôi
Câu 2 là bài toán Phân công lao động, giải bằng tham ăn hoặc nhánh cận
Câu 3 tương tự bài tam giác số, cũng có 2,3 cách giải
Tham khảo tại:
th-cam.com/channels/8HHhH_Pa6_l-eaieKzjlSw.html
Hay quá thầy ơi!!
Cảm ơn em
cảm ơn thầy
Cảm ơn em
Em xe mvideo này vào năm 2023 để học c++ tốt hơn ạ,
=))))))))))))))))))))))))))))))))))))))
Chúc em học giỏi thành công
Tuyệt vời lắm thầy ạ
Cảm ơn em đã động viên. Sắp tới tôi dự kiến sẽ có các video bài giảng về cấu trúc dữ liệu, cũng sẽ post lên kênh này luôn.
Dạ nếu trong lúc xét Max của các giá trị xk nếu có 2 giá trị max bằng nhau thì mình chọn xk như thế nào v ạ
Theo lệnh chọn FMax đã trình bày:
if(F[k-1][V-xk*(int)dsdv[k].TL]+xk*dsdv[k].GT>FMax){
FMax=F[k-1][V-xk*(int)dsdv[k].TL]+xk*dsdv[k].GT;
XMax= xk;
}
thì nếu có nhiều xk làm cho giá trị FMax lớn bằng nhau thì chon xk đầu tiên. Nếu muốn chọn xk sau cùng thì thay dấu > bằng dầu >= trong biểu thức của if.
hay quá thầy ơi
Cảm ơn em đã động viên
em mới đi pv chắc là tạch thuật toán :(( h về học lại học thầy cho vững
cho e hỏi mình giải phương trình như thế nào mà T(n) = O(2^n) vậy thầy?
Giải phương trình T(1)=C1 và T(n)= 2T(n-1)+C2
Ta có T(n)= 2T(n-1)+C2= 2[2T(n-2)+C2]+C2 (vì T(n-1)= 2T(n-2)+C2
=> T(n)= 4T(n-2)+3C2= 4[2T(n-3)+C2]+3C2= 8T(n-3)+7C2 = ….2^iT(n-i)+(2^i-1)C2 (1)
Quá trình kết thúc khi n-i=1 hay i=n-1 thay vào (1) ta được
T(n)= 2^(n-1)T(1) + [2^(n-1)-1]C2= 2^(n-1)C1 + 2^(n-1)C2 - C2= (C1+C2)2^(n-1)-C2= O(2^n)
Thưa Thầy, có thể cho em biết X[k,V] và các xi trong biểu thức F[n,W]=F[n]=x1*v1+x2*v2+...+xn*vn khác biệt gì nhau ạ?
X[k,V] là số lượng đồ vật thứ k được chọn ứng với trong lượng còn lại của ba lô là V sao cho F[k,V] lớn nhất. Còn xi trong hàm mục tiêu F(n)=x1*v1+x2*v2+...+xn*vn là số lượng đồ vật thứ i được chọn ứng với trọng lượng được cho ban đầu W của ba lô. Mục tiêu chúng ta phải chọn các xi sao cho F(n) lớn nhất. Mà F(n) chính là F[n,W]. Vậy để cho F(n)=F[n,W] lớn nhất thì phải chọn mọi F[k,V] cũng phải lớn nhất (k=1->n, V=0->W). Từ đó ta xây dựng được bảng F và bảng X (tạo bảng). Căn cứ vào bảng X mà ta tìm được phương án (tra bảng) X= (x1, x2, ..., xn)
tổng giá trị mình có thể lấy là F(n,v) không thầy
F(n,v) là tổng giá trị n loại đồ vật dduwwojc chọn, ứng với trọng lượng còn lại của ba lô là v => Tổng giá trị của n lọai đồ vật được chọn, ứng với trọng tải ban đầu của ba lô W là F(X)=F(n,W)
thầy ơi cho em xin tài liệu về quy hoạch động với ạ !!!
Nếu như đệ quy kết hợp lưu giá trị của mảng thì độ phức tạp có gần bằng qhd k ạ
Em có thể cho ví dụ về sự kết hợp này thì tôi mới trả lời câu hỏi của em được
@Cấu trúc Dữ liệu và Giải thuật - Nguyễn Văn Linh ví dụ như là hàm tính tổ hợp c(int n,int k) ạ
Nếu chạy bình thường thì sẽ bị tính lại 1 cái nhiều lần (ví dụ như đoạn 7:49 có 2 cái Comb(2,1) ạ)
Thì mình tạo thêm một mảng a[n+1][k+1] và đặt tất cả giá trị là -1
Xong r cho thêm lệnh ở ngay đầu tiên của hàm c(n,k) là:
Nếu (a[n][k] khác -1) return a[n][k];
Còn nếu không thì tính c(n,k) r gán vào a[n][k]
Cách này có áp dụng đc nhiều dạng bài k ạ, hay một số bài thì thời gian của nó chậm hơn rất nhiều so với qhd ạ
@@giyu4103 Vấn đề là hàm tính c(n,k) như thế nào. Vì độ phức tạp phụ thuộc vào thuật toán tính c(n,k). Em viết code đầy đủ mới thấy được
@@cautrucdulieuvagiaithuat-n6504 em lấy ví dụ là bài toán ở trong video ạ, c(n,k)=c(n-1,k-1) + c(n-1,k)
@@giyu4103 đây là công thức toán học thôi. Code theo đệ quy thì có độ phức tạp O (2^n), theo quy hoạch động thì O (n^2). Trong video đã trình bày như thế. Nhưng em nói kết hợp giữa đệ quy và lập bảng thì em viết code cụ thể gửi tôi xem
Thầy đang viết trên ngôn ngữ C++ phải k ạ
Chỉ là C thôi nha em
Thầy cho em xin tài liệu ạ!
Thầy giống người nghệ an vậy thầy
Đúng rồi em
@@cautrucdulieuvagiaithuat-n6504 e cũng người nghệ an
@@phuong15101985 THế à, quê tôi ở Thanh Chương, em quê ở đâu?
ban o dau nghe an
dạ thầy ơi, phút thứ 26:50 em thắc mắc tại sao 'xk' lại thay đổi từ 0 đến 'V/gk'.Lúc này đồ vật thứ 'k' sẽ có trọng lượng là 'V' thì V=xk.gk==>xk=V/gk, mà V chạy từ 0 đến W, vậy thì 'xk' sẽ chạy từ 0 đến W/gk phải không thầy?
xk chạy từ 0 đến W/gk chỉ là các xk ứng với 1 trường hợp trọng tải của ba lô W. Còn xk chạy từ 0 đến V/gk với mọi V từ 0 đến W là xét hết tất cả các trường hợp trọng tải của ba lô V
@@cautrucdulieuvagiaithuat-n6504 dạ, cảm ơn thầy đã giải đáp ạ
Thầy ơi có tài liệu hay hay gởi cho tụi con xin đi thầy.
Thầy đang về quê, vài bữa nữa vào CT mới gửi cho em được. Cụ thể em cần tài liệu gì
@@cautrucdulieuvagiaithuat-n6504 em đang cần tài liệu ôn nâng cao các thuật toán của pascal. Để ôn cho mấy em thpt. Thầy có cho em xin. Cám ơn thầy nhiều.
@@alibaba200405 Em cho địa chi email để thầy gửi
@@cautrucdulieuvagiaithuat-n6504 alibaba200405@gmail.com cám ơn thầy trước nhé. 🤗🤗🤗🤗🤗
@@alibaba200405 Thầy mới gửi mail
Thầy ơi con đag ôn thi tin, thầy có thể cho con xin một số tài liệu về quy hạch động pascal đc không ạ
Mail con là
lythuang823@gmail.com
Con cảm ơn bài giảng của thầy ạ
Tôi đã gửi tài liệu cho em
Bài giảng của thầy rất hay ạ! Thầy cho em xin slide với ạ gmail: nguyenthuylinh040205@gmail.com
. Em cảm ơn ạ
Thầy đã gửi mail cho em
@@cautrucdulieuvagiaithuat-n6504 em cảm ơn ạ
cảm ơn thầy
Cảm ơn em nhiều