thuật toán cơ bản bằng chứng

Question

Tôi có một chuỗi các con số, ví dụ: 170, 205, 225, 190, 260, 130, 225, 160 và tôi phải chia chúng thành bộ với số lượng cố định các yếu tố để các tối đa chênh lệch giữa các yếu tố của các bộ được giảm thiểu.

Tôi có đảm bảo rằng nếu tôi cần chia các phần tử thành bộ các phần tử K thì số phần tử tổng thể bằng Z * K.

Đối với ví dụ với K = 4, tách tối ưu có thể được perfomed theo cách này:

(1) : 130 160 170 190(chênh lệch tối đa bằng 60)

(2) : 205 225 225 260(chênh lệch tối đa bằng 55)

Vì vậy, chênh lệch tối đa toàn cầu cho trường hợp này bằng 60.

---

Bây giờ, câu hỏi: là giả định của tôi mà tôi có thể chỉ đơn giản là loại các dữ liệu ban đầu và chia nó thành thậm chí phần bắt đầu từ đầu? Nếu điều này là chính xác, làm thế nào tôi có thể chứng minh điều đó? Và nếu không, tôi nên sử dụng phương pháp nào để giải quyết vấn đề này?

Answer 1

Giả sử số lượng các số của bạn luôn có thể được chia chính xác bằng K (không phải 13 số trong bộ 4), nó là chính xác.

Thông qua sắp xếp, bạn sẽ nhận được những con số tương tự nhất gần nhau nhất có thể, rõ ràng. Câu hỏi đặt ra là, nếu các con số được di chuyển để mang lại giá trị đặt tồi tệ nhất trong một tập hợp với các giá trị gần hơn, điều đó có làm cho sự khác biệt tối đa nhỏ hơn không?

Câu trả lời là không. Khi được sắp xếp, các giá trị duy nhất ở bên trái của số bằng hoặc thấp hơn, số sẽ di chuyển sang bên trái sẽ được bao quanh bởi các giá trị thấp hơn. Trong số hai con số gây ra sự khác biệt tối đa, ít nhất một số sẽ nhận được một đối tác tồi tệ hơn, có nghĩa là khoảng cách tối đa của bạn sẽ trở nên cao hơn. Nó hoạt động theo cùng một cách với các con số cao hơn ở bên phải.

Sorted: 
[lowest, low, low, x] distance1 = x-lowest 
[y, high, high, highest] distance2 = highest-y 

Swapped: 
[lowest, low, low, y] distance3 = y-lowest 
[x, high, high, highest] distance4 = highest-x 

Kể từ x < y (hãy giả sử họ không giống nhau khi trao đổi sẽ là vô nghĩa), distance3> distance1 và distance4> distance2, có nghĩa là mọi việc trở nên tồi tệ hơn.

Nó hoạt động theo cách tương tự nếu bạn đặt giá trị cao hơn ở đó.

Không có vấn đề làm thế nào tắt một số, đặt một số khác tại chỗ đó sẽ làm cho chúng nhiều hơn.

Một lựa chọn khác là để di chuyển toàn bộ tập hợp con một không gian còn lại:

[lowest, low, low, y] 
[high, high, highest, x] 

Nhưng điều này thực sự là kết quả tương tự như trao đổi.

Vì vậy, đó là cách nó hoạt động với 2 bộ.

Với ba bộ:

[lowest, low, low, x] 
[lowM, lowM, highM, highM] 
[highM, y, high, highest] 

Trao đổi x và y là giống như trước đó. Ngay cả khi x là rất giống nhau hoặc thậm chí bằng đáy trái cao (nếu mức trung bình thấp và cao thực sự bằng nhau), y vẫn cao hơn x, tạo sự khác biệt lớn nhất thấp hơn, và x là xa hơn.

Di chuyển một loạt các con số chuyển tiếp:

[lowest, low, lowM, lowM] 
[highM, highM, highM, y] 
[x, highM, high, highest]; 

Có lẽ sự khác biệt lớn nhất là giữa highM và cao nhất, và khoảng cách mà bây giờ được lấy ra. Nhưng kể từ khi bạn chỉ có thể di chuyển nó ra khỏi cao nhất bằng cách đặt một giá trị thậm chí thấp hơn ở đó, bạn luôn luôn làm cho nó tồi tệ hơn. Khoảng cách cao nhất cao nhất cao nhất hiện cao nhất-x và cao hơn x < highM.

Nó vẫn hoạt động theo cách khác. Đã có một tập tiếp theo, highM có thể được đổi chỗ với một số cao hơn gần với cao nhất, nhưng điều này sẽ đặt highM với số thậm chí cao hơn gây ra một sự khác biệt lớn hơn.

Vì vậy, có, phân loại dữ liệu và sau đó chia nhỏ nó bằng các phần bằng nhau luôn mang đến cho bạn sự khác biệt tối đa tối thiểu, vì việc thay đổi các bộ sắp xếp luôn mang lại kết quả tồi tệ hơn.Lưu ý: Nếu K không thể chia các con số, nó sẽ phức tạp hơn, bạn sẽ phải tìm ra tập hợp tồi tệ nhất và xem liệu bạn có thể di chuyển số cao nhất hoặc thấp nhất sang tập tiếp theo hoặc trước đó mà không cần thực hiện khác đặt một sự khác biệt tồi tệ hơn. Quy tắc mà bạn chỉ có thể trao đổi số thấp với số cao bị xóa, vì bạn có thể trao đổi chúng với số không, vì vậy việc chứng minh mọi thứ về điều đó là một cấp độ hoàn toàn mới.

Answer 2

Nếu trình tự ban đầu được sắp xếp thì các số liền kề phải có sự khác biệt nhỏ nhất.

Ngoài ra, các phần tử ở đầu và cuối chuỗi phải có sự khác biệt lớn nhất.

Kết quả là bất kỳ "cắt" nào của chuỗi bao gồm phần tử cuối cùng và phần tử đầu tiên không thể là một phần của giải pháp vì nó bao gồm một sự khác biệt không ở mức tối thiểu.

Vì vậy, việc chia nhỏ phải được thực hiện bằng cách chia chuỗi các số thành các phần ngay cả khi bắt đầu.

Dường như với tôi cách tiếp cận của bạn là chính xác, nhưng tôi không thể nghĩ ra một bằng chứng chính thức hơn cho việc này.

Answer 3

Đương nhiên, bạn sẽ nhận được sự khác biệt nhỏ nhất giữa các cặp số bằng cách sắp xếp chúng. Bạn có thể nhận được các bộ với sự khác biệt nhỏ nhất bằng cách chia nhỏ các số được sắp xếp.

Trong một số trường hợp, bạn có thể chuyển đổi số giữa các bộ mà không tăng tối đa mỗi bộ, vì vậy có thể có nhiều cách chia số thành tập hợp có cùng mức chênh lệch tối đa. Tuy nhiên, bạn không thể chuyển đổi số giữa các bộ để giảm tối đa của một trong hai bộ mà không tăng tối đa của bộ khác.

Nếu bạn ví dụ có bộ 1,3,4,5 và 6,7,8,10, sau đó bạn có thể chuyển đổi các 5 và 6 mà không làm tăng chênh lệch tối đa ở cả hai nhóm.

Nếu bạn muốn nhỏ nhất trung bình của sự khác biệt, thì bạn có thể hy sinh sự khác biệt tối đa trong một tập hợp để giảm sự khác biệt trong tập hợp khác.