30/09/2018, 18:12
Hướng dẫn cách giải bài Người đánh cá Clement
Đề: Người đánh cá Clement bắt được n con cá, khối lượng mỗi con là ai, đem bán ngoài chợ. Ở chợ cá, người ta không mua cá theo từng con mà mua theo một lượng nào đó. Chẳng hạn 3 kg, 5kg… Ví dụ: có 3 con cá, khối lượng lần lượt là: 3, 2, 4. Mua lượng 6 kg sẽ phải lấy con cá thứ 2 và và thứ 3. Mua lượng 3 kg thì lấy con thứ nhất. Không thể mua lượng 8 kg. Nếu bạn là người đầu tiên mua cá, có bao nhiêu lượng bạn có thể chọn?
Ai đó hướng dẫn em giải bài này với phương pháp quy hoạch động? Cụ thể là cách xây dựng công thức
Xin cảm ơn!!!
Bài liên quan
bài này mình nghĩ là sinh tổ hợp rồi đếm số TH của tổ hợp tạo thành
code tham khảo: http://ideone.com/9CDhHj
có 7 lượng nhỉ??? đầu tiên mua 1 con nên có 3 lượng, mua 2 con cũng có 3 lượng còn mua 3 con có 1 lượng. Mình nghĩ thế!!
Với phương pháp quy hoạch động thì sao bạn?
Không dễ vậy đâu
Nếu chọn một con thì có 3 cách : 1kg 2kg 3kg
Nếu chọn hai con thì có hai cách: 4kg 5kg (2kg + 1kg = 3kg bị trùng)
Nếu chọn ba con thì có một cách: 6kg
Nếu Ai nhỏ thì có thể dùng qhd. DPT O(n^2 *max(Ai))
Ideone.com
Ideone.com
Ideone is something more than a pastebin; it's an online compiler and debugging tool which allows to compile and run code online in more than 40 programming languages.
Bạn nói rõ cách làm được không? Mình không học Pascal nên không hiểu C lắm
Dung mang value để đánh dấu các giá trị của tổng có thể có. Tại mỗi lần duyệt Ai luư 1 mảng giá trị mới dc tạo thành, sau đó cập nhật vào mảng đánh dấu.
Sau đó đếm các giá trị có thể xảy ra là số th có dc
Đây gọi là vét cạn hả ae
Dùng vét cạn cũng được, nhưng yêu cầu là phải dùng quy hoạch động
Có cách nào để xây dựng bài toán trên với một mảng a hai chiều (m*n), sau khi giải xong thì phần tử cuối cùng của mảng a[m,n] là số cách chọn lớn nhất.