Xây dựng thuật toán tìm tập S* sao cho các đoạn thẳng trong S* đôi một không có điểm chung mà có tổng độ dài các đoạ

[vannhan]

Em được giao một bài tập lớn như sau :

Mỗi đoạn thẳng trên trục Ox được mô tả bởi hai giá trị [a, b]. Kí hiệu S là tập hợp n đoạn
thẳng S = {[ai,bi], i = 1,2,...,n}. Xây dựng thuật toán tìm tập S* sao cho các đoạn thẳng trong
S* đôi một không có điểm chung mà có tổng độ dài các đoạn thẳng là lớn nhất.

Em chưa nghĩ ra hướng đi của bài toán. Mọi người có ý tưởng gì gọi ý giúp em

[tiendaotd]

bước 1: nếu giới hạn a, b lớn thì bạn rời rạc hóa để chuyển các tọa độ a[i], b[i] về giới hạn nhỏ, cỡ 2*n.

bước 2: sort lại các đoạn thẳng theo a, nếu a bằng nhau thì sort tăng theo b

bước 3: sau đó xử lý bằng Quy hoạch động như sau: gọi f[x] là tổng độ dài lớn nhất của các đoạn thẳng không giao nhau, và đoạn thẳng cuối cùng có b = x. Với mỗi đoạn thẳng i có cận dưới là ai, bạn duyệt tìm xem từ f[0] tới f[ai-1] xem cái nào lớn nhất, sau đó cập nhật f[bi] = (f max tìm được) + (độ dài đoạn i)

Tùy vào cách tìm đoạn f max lớn nhất mà thuật toán của bạn sẽ có độ phức tạp là n^2 hoặc n*logn. Kết quả bài toán là max của các f[bi]

[vannhan]

bước 1: nếu giới hạn a, b lớn thì bạn rời rạc hóa để chuyển các tọa độ a[i], b[i] về giới hạn nhỏ, cỡ 2*n.

bước 2: sort lại các đoạn thẳng theo a, nếu a bằng nhau thì sort tăng theo b

bước 3: sau đó xử lý bằng Quy hoạch động như sau: gọi f[x] là tổng độ dài lớn nhất của các đoạn thẳng không giao nhau, và đoạn thẳng cuối cùng có b = x. Với mỗi đoạn thẳng i có cận dưới là ai, bạn duyệt tìm xem từ f[0] tới f[ai-1] xem cái nào lớn nhất, sau đó cập nhật f[bi] = (f max tìm được) + (độ dài đoạn i)

Tùy vào cách tìm đoạn f max lớn nhất mà thuật toán của bạn sẽ có độ phức tạp là n^2 hoặc n*logn. Kết quả bài toán là max của các f[bi]

Cảm ơn bác, em hiểu cách làm rồi .

Em đã làm xong bài này. Post lên cho mọi người tham khảo

[s0978338707]

b ơi mình chạy code báo k tìm thấy file text

[khoaph]

bước 1: nếu giới hạn a, b lớn thì bạn rời rạc hóa để chuyển các tọa độ a[i], b[i] về giới hạn nhỏ, cỡ 2*n.

bước 2: sort lại các đoạn thẳng theo a, nếu a bằng nhau thì sort tăng theo b

bước 3: sau đó xử lý bằng Quy hoạch động như sau: gọi f[x] là tổng độ dài lớn nhất của các đoạn thẳng không giao nhau, và đoạn thẳng cuối cùng có b = x. Với mỗi đoạn thẳng i có cận dưới là ai, bạn duyệt tìm xem từ f[0] tới f[ai-1] xem cái nào lớn nhất, sau đó cập nhật f[bi] = (f max tìm được) + (độ dài đoạn i)

Tùy vào cách tìm đoạn f max lớn nhất mà thuật toán của bạn sẽ có độ phức tạp là n^2 hoặc n*logn. Kết quả bài toán là max của các f[bi]

Nếu có hơn 1 đoạn có cận trên bi=x thì lấy cái ai nào nhỉ?