Giải thuật vét cạn sắp xếp các truyện ngắn sao cho tổng số truyện bắt đầu từ trang lẻ là lớn nhất

[GeoHot]

Một quyển sách truyện có n truyện ngắn. Mỗi truyện ngắn chiếm lần lượt a1,a2, ....an trang giấy. Các truyện được in từ trang 1, mỗi truyện mới được in từ đầu trang tiếp theo. Hãy sắp xếp các truyện sao cho số lượng các truyện bắt đầu từ trang lẻ là:
a) Lớn nhất.
b) Nhỏ nhất.

Mình đang làm đồ án CTDL với đề như trên.
Thuật toán thì mình dùng backtrack để liệt kê các cấu hình thỏa mãn yêu cầu đề bài với:
K + (n-k)/2 nếu n-k là chẵn
MAX(x)=
K + (n-k+1)/2 nếu n-k là lẻ
Với k:tổng số truyện có số trang chẵn
Công thức trên là do mình suy luận ra nhưng chưa chứng minh được, pro nào biết cách CM hoặc có giải thuật nào khác thì chỉ cho mình với.
Thanks

[clchicken]

Mình có cùng tư tưởng với bạn .
Mới đầu chọn ngay vị trí trang 1. Đặt liên tiếp toàn bộ số truyện chẵn trang vào . Nếu gọi k là số truyện chẵn trang thì k sẽ dc sử dụng hết sau khi làm việc này.
Kết thúc việc này thì trang tiép theo để bắt đầu dán truyện vào sẽ là trang LẺ

Sau đó chỉ còn lại (n-k) số truyện là lẻ trang.
Truyện bắt đầu từ lẻ(chẵn), lại lẻ trang thì trang tiếp theo để in truyện khác lại là chẵn(lẻ).
Do đó số truyện dc bắt đầu ở trang lẻ trong số (n-k) còn lại này chỉ còn 1/2 (hoặc 1/2 + 1) .
Nếu suy nghĩ theo phương thức này thì lý giải như thế.
Vấn đề ở đây là ko biết cách này có cho ra kết quả Max ko thôi :P ^^
Giải quyết = việc trả lời câu hỏi : Có cách nào đặt truyện chẵn trang và truyện lẻ trang theo 1 quy luật nào đó (Có thể là xen kẽ) để sao cho tận dụng dc (n-k) số truyện còn lại với 1 khả năng > (lớn hơn) 1/2 như cách trên

Bấc giác nghĩ đến vét cạn kiểu cùi bắp vơi tư duy của lý thuyết phép đếm : Mình cho ra thuật toán vét cạn với độ phức tạp n! , thấy khủng khiếp quá nên thôi


//----------

Mình chứng minh như sau :
Gọi L là tổng truyện lẻ trang, C là tổng số truyện chẵn trang
1)Nếu dùng phép đặt các truyện lẻ trang và chẵn trang xen kẽ nhau trên khoảng nào đó . Kể cả trong 2 trường hợp là truyện lẻ trang đặt trước vào vị trí trang lẻ, hoặc đặt trước vào trang chẵn thì.
Nếu gọi T=L'+C' là tổng số truyện đã đặt lên đoạn đó, L' (C') là tổng truyện lẻ(chẵn) trang đã dc đặt lên. thì kết quả số truyện dc đặt vào trang lẻ tối đa là (L'+C')/2 . hoặc (L'+C'+1)/2
Vậy hiệu suất của phép này là 50% đối với L và 50% với C.
2)Nếu dùng phương pháp đặt liên tiếp số truyện chẵn trang(chỉ tính phần của số truyện chẵn trang này thôi,số truyện lẻ trang còn lại chưa bàn) , bắt đầu từ trang lẻ .
Hiệu suất là 100% C .
Nếu bắt đầu từ trang chẵn, hiệu suất là 0% C
3)Nếu dùng phương pháp đặt liên tiếp số truyện lẻ trang(số truyện chẵn trang chưa bàn), bất kể bắt đầu từ chẵn hay lẻ đều cho hiệu suất 50% L.

--
Trong việc xắp xếp với 2 loại phần tử này chỉ có 2 kiểu: 1 là liên tiếp , 2 là xen kẽ.
Bằng quy nạp ta sẽ chứng minh dc nếu càng đặt xen kẽ bao nhiêu thì hiệu suất sẽ giảm bấy nhiêu so với đặt liên tiếp(trường hợp vấn đề 2)

Vì thế cách đặt liên tiếp cho ra kết quả với hiệu suất cao nhất
-----------------------
Đôi lời ngu ý của mình thế :(

[GeoHot]

Cảm ơn bạn đã bỏ thời gian suy nghĩ
Theo mình,
Có nhiều cách đế sắp xếp thỏa yêu cầu đề bài chứ ko phải 2 kiểu như bạn nói.
Cách sắp k truyện chẵn đầu tiên rồi đến n-k truyện lẻ chỉ là 1 cách sắp xếp thỏa. Từ đó để mình suy ra CT như trên.
Cách CM của bạn bằng quy nap bạn có thể nói rõ hơn dc ko, mình chưa hiểu rõ cách suy luận của bạn

[clchicken]

Cảm ơn bạn đã bỏ thời gian suy nghĩ
Theo mình,
Có nhiều cách đế sắp xếp thỏa yêu cầu đề bài chứ ko phải 2 kiểu như bạn nói.
Cách sắp k truyện chẵn đầu tiên rồi đến n-k truyện lẻ chỉ là 1 cách sắp xếp thỏa. Từ đó để mình suy ra CT như trên.
Cách CM của bạn bằng quy nap bạn có thể nói rõ hơn dc ko, mình chưa hiểu rõ cách suy luận của bạn

Không . 2 cách trên tức là xếp liên tiếp hoặc xen kẻ với 2 loại truyện lẻ trang và chẵn trang là mnhf đang nói ở trường hợp nguyên tử. Tức là chỉ có 2 truyện đang dc sắp xếp. . Và nếu tổng quát 2 cách trên thì dc hiệu suất như mình đã nói
Trong 1 dãy n truyện cần sắp thì cách sắp như nào chưa cần biết, nhưng cách nào rồi cũng luôn luôn phải dc cấu thành từ 2 phép sắp xếp nguyên tử này.
Ví dụ phép sắp : Lẻ - Chẵn - Lẻ- lẻ-Chẵn-Chẵn -chẵn-chẵn
Thì phép sắp này dc cấu thành từ 3 phép sắp nguyen tử xen kẽ , 1 phép sắp nguyên tử liên tiếp lẻ và 3 phép sắp nguyên tử liên tiếp chẵn

Bạn tìm dc vấn đề nguyên tử trong bài toán thì bạn có thể dùng quy nạp để chứng minh dc rùi .
Còn ko thì chứng minh theo lối đệ quy, từ không gian lớn n , bạn chứng minh đệ quy dần xuống chỉ còn 2.