thảo luận [Học Tập] Topic thuật toán

Giam Doc EVN · 25/12/21

Seeder_Intel đã nói:
Mình có 1 cái problem như hình, có runtime constraint nên không thể brute force được, các ae vào giúp đỡ. Mình cám ơn

Các ae lưu ý là 2 là winter chứ k phải summer

Xin nốt cái example luôn. Đọc sơ qua thì hướng giải quyết có thể là greedy algorithm.

Seeder_Intel · 25/12/21

Giam Doc EVN đã nói:
Xin nốt cái example luôn. Đọc sơ qua thì hướng giải quyết có thể là greedy algorithm.

Seeder_Intel · 25/12/21

Giam Doc EVN đã nói:
Xin nốt cái example luôn. Đọc sơ qua thì hướng giải quyết có thể là greedy algorithm.

Mình không nghĩ là dùng pure greedy được do nó có cái subset số 3 ( cái cả 2 ss) thì không biết dùng greedy như nào

Giam Doc EVN · 25/12/21

Seeder_Intel đã nói:
Mình không nghĩ là dùng pure greedy được do nó có cái subset số 3 ( cái cả 2 ss) thì không biết dùng greedy như nào

Chính xác là phải dùng dynamic programming để giải

Seeder_Intel · 25/12/21

Giam Doc EVN đã nói:
Chính xác là phải dùng dynamic programming để giải

Là sao thím ơi, mình cũng không hiểu cho lắm

Giam Doc EVN · 25/12/21

Seeder_Intel đã nói:
Là sao thím ơi, mình cũng không hiểu cho lắm

Bài này có thể giải theo 2 cách, dùng recursion hoặc dynamic programming. Cơ bản là mình phải tìm ra tất cả giá trị p (có thể có rất nhiều p) có thể xảy ra với a và b cho trước. Sau cùng là tìm ra giá trị p lớn nhất.
Mấy bài toán dùng DP chưa bao giờ là dễ giải. Cần nhiều thời gian để suy nghĩ

Seeder_Intel · 25/12/21

Giam Doc EVN đã nói:
Bài này có thể giải theo 2 cách, dùng recursion hoặc dynamic programming. Cơ bản là mình phải tìm ra tất cả giá trị p (có thể có rất nhiều p) có thể xảy ra với a và b cho trước. Sau cùng là tìm ra giá trị p lớn nhất.
Mấy bài toán dùng DP chưa bao giờ là dễ giải. Cần nhiều thời gian để suy nghĩ

Dùng recursion như nào vậy thím ơi, thử hết value trong cái subset thứ 3 ( cả 2 season) à ?

_Gia_Cat_Luong_ · 25/12/21

Seeder_Intel đã nói:
Dùng recursion như nào vậy thím ơi, thử hết value trong cái subset thứ 3 ( cả 2 season) à ?

Đúng rồi, với mỗi item cứ thử cả 3 trường hợp:

Không mua nó (save cost)
Mua vào summer (nếu được)
Mua vào winter (nếu được)

Kết quả là max của 3 trường hợp này.
Mã giả cho bạn tham khảo, DP thì cứ memoiz cái hàm này thôi:

Mã:

maxPoint(i, cw, cs) { // Xét item thứ i, với số tiền còn lại cho mùa đông (cw) và mùa hạ (cs)
    if (i >= n) return 0;
    p = maxPoint(i + 1, cw, cs) // không mua item

    if (s[i] & 1 && c[i] <= cs) { // mua mùa hạ
        p = max(p, p[i] + maxPoint(i + 1, cw, cs - c[i]))
    }

    if (s[i] & 2 && c[i] <= cw) { // mua mùa đông
        p = max(p, p[i] + maxPoint(i + 1, cw - c[i], cs))
    }

    return p
}

Seeder_Intel · 25/12/21

_Gia_Cat_Luong_ đã nói:
Đúng rồi, với mỗi item cứ thử cả 3 trường hợp:

Không mua nó (save cost)

Mua vào summer (nếu được)

Mua vào winter (nếu được)

Kết quả là max của 3 trường hợp này.
Mã giả cho bạn tham khảo, DP thì cứ memoiz cái hàm này thôi:

Mã:

maxPoint(i, cw, cs) { // Xét item thứ i, với số tiền còn lại cho mùa đông (cw) và mùa hạ (cs) if (i >= n) return 0; p = maxPoint(i + 1, cw, cs) // không mua item if (s[i] & 1 && c[i] <= cs) { // mua mùa hạ p = max(p, p[i] + maxPoint(i + 1, cw, cs - c[i])) } if (s[i] & 2 && c[i] <= cw) { // mua mùa đông p = max(p, p[i] + maxPoint(i + 1, cw - c[i], cs)) } return p }

Cám ơn bạn, nhân tiện cho mình hỏi, bài này độ khó chắc tầm medium trên leetcode nhỉ ?

_Gia_Cat_Luong_ · 25/12/21

Seeder_Intel đã nói:
Cám ơn bạn, nhân tiện cho mình hỏi, bài này độ khó chắc tầm medium trên leetcode nhỉ ?

Hard for sure luôn bạn

Mazda Support · 25/12/21

Giam Doc EVN đã nói:
Bài này có thể giải theo 2 cách, dùng recursion hoặc dynamic programming. Cơ bản là mình phải tìm ra tất cả giá trị p (có thể có rất nhiều p) có thể xảy ra với a và b cho trước. Sau cùng là tìm ra giá trị p lớn nhất.
Mấy bài toán dùng DP chưa bao giờ là dễ giải. Cần nhiều thời gian để suy nghĩ

recursion thì cũng là DP thôi chứ

Seeder_Intel · 25/12/21

_Gia_Cat_Luong_ đã nói:
Hard for sure luôn bạn

Cám ơn bạn nhiều

Donald Trump USA_No1 · 25/12/21

_Gia_Cat_Luong_ đã nói:
Hard for sure luôn bạn

Bạn luyện kiểu gì mà giỏi thế nhỉ, mình easy còn chưa làm đc

_Gia_Cat_Luong_ · 25/12/21

Donald Trump USA_No1 đã nói:
Bạn luyện kiểu gì mà giỏi thế nhỉ, mình easy còn chưa làm đc

Chăm chỉ + có lộ trình rõ ràng là được thôi bạn.
Level đi thi này nọ thì khó chứ mức medium và mấy bài hard bth trên LC thì mình nghĩ ai luyện 1 tgian đủ lâu đều có thể làm được.

p/s: đủ lâu = khoảng 1-2 năm liên tục nha

Donald Trump USA_No1 · 25/12/21

_Gia_Cat_Luong_ đã nói:
Chăm chỉ + có lộ trình rõ ràng là được thôi bạn.
Level đi thi này nọ thì khó chứ mức medium và mấy bài hard bth trên LC thì mình nghĩ ai luyện 1 tgian đủ lâu đều có thể làm được.

p/s: đủ lâu = khoảng 1-2 năm liên tục nha

Bác chia sẻ rõ được k ạ, kiểu trước bác có follow lộ trình nào ko?

Em chỉ cần luyện để làm thành thục medium đi phỏng vấn là tốt rồi chứ em ko đi thi

_Gia_Cat_Luong_ · 25/12/21

Donald Trump USA_No1 đã nói:
Bác chia sẻ rõ được k ạ, kiểu trước bác có follow lộ trình nào ko?

Em chỉ cần luyện để làm thành thục medium đi phỏng vấn là tốt rồi chứ em ko đi thi

Lộ trình sơ sơ thì trước minh cũng share trong thớt này vài lần rồi, thím có thể search lại.

Còn lộ trình chi tiết thì dài dòng lắm, nếu thím thật sự cần thiết và quyết tâm thì có thể hộp mình hướng dẫn cho, vì nói thật 2 chữ chăm chỉ tuy đơn giản nhưng rất khó làm được.

Giam Doc EVN · 25/12/21

Seeder_Intel đã nói:
Cám ơn bạn, nhân tiện cho mình hỏi, bài này độ khó chắc tầm medium trên leetcode nhỉ ?

Mấy bài kiểu này nếu bạn không phải một coder có kinh nghiệm đang muốn thử thách bản thân thì nên bỏ qua. DP hại não vl

Mazda Support đã nói:
recursion thì cũng là DP thôi chứ

2 kỹ thuật có thể dùng chung cho 1 mục đích nhưng phương thức hoạt động khác nhau. Thông thường, DP là phiên bản cải tiến của recursion.

Donald Trump USA_No1 · 25/12/21

_Gia_Cat_Luong_ đã nói:
Lộ trình sơ sơ thì trước minh cũng share trong thớt này vài lần rồi, thím có thể search lại.

Còn lộ trình chi tiết thì dài dòng lắm, nếu thím thật sự cần thiết và quyết tâm thì có thể hộp mình hướng dẫn cho, vì nói thật 2 chữ chăm chỉ tuy đơn giản nhưng rất khó làm được.

Bác cho em hỏi em dùng C# để luyện algo, mà xử lý array trong C# kiểu thêm phần tử các thứ k dễ như JS thì em có đc convert sang List để cho tiện Add Remove khi phỏng vấn k nhỉ

_Gia_Cat_Luong_ · 26/12/21

Donald Trump USA_No1 đã nói:
Bác cho em hỏi em dùng C# để luyện algo, mà xử lý array trong C# kiểu thêm phần tử các thứ k dễ như JS thì em có đc convert sang List để cho tiện Add Remove khi phỏng vấn k nhỉ

Được thôi bạn, mấy cái này không quan trọng lắm đâu

Mazda Support · 26/12/21

Giam Doc EVN đã nói:
Mấy bài kiểu này nếu bạn không phải một coder có kinh nghiệm đang muốn thử thách bản thân thì nên bỏ qua. DP hại não vl

2 kỹ thuật có thể dùng chung cho 1 mục đích nhưng phương thức hoạt động khác nhau. Thông thường, DP là phiên bản cải tiến của recursion.

tôi nghĩ anh nhầm rồi, DP là phương pháp giải quyết bài toán, recursion ở đây là cách lập trình thôi, 2 cái không phải cùng 1 phạm trù

thảo luận [Học Tập] Topic thuật toán

Đã tốn tiền

Senior Member

Senior Member

Đã tốn tiền

Senior Member

Đã tốn tiền

Senior Member

Senior Member

Senior Member

Senior Member

Senior Member

Senior Member

Senior Member

Senior Member

Senior Member

Senior Member

Đã tốn tiền

Senior Member

Senior Member

Senior Member

Chủ đề tương tự

Thống kê chủ đề

Chia sẻ trang này