Hướng dẫn cách giải bài Người đánh cá Clement

#1

Đề: 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!!!

1 Like
#2

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

#3

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ế!!

1 Like
#4

Với phương pháp quy hoạch động thì sao bạn?

#5

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

#6

Nếu Ai nhỏ thì có thể dùng qhd. DPT O(n^2 *max(Ai))

#7

Bạn nói rõ cách làm được không? :grinning: Mình không học Pascal nên không hiểu C lắm

#10

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

1 Like
#11

Đây gọi là vét cạn hả ae :smile:

#12

Dùng vét cạn cũng được, nhưng yêu cầu là phải dùng quy hoạch động :smiley_cat:

1 Like
#13

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.

83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?