Tìm một kết quả phù hợp của hai danh sách số

Question

Tôi nhận được hai bộ số, với SET2 có nhiều mục hơn trong số đó. Đảm bảo rằng số lượng SET2 bằng hoặc lớn hơn số lượng SET1. Về mặt lý thuyết, vì thứ tự quan trọng, đầu vào là danh sách thay vì các bộ.

Mục tiêu của tôi là kết hợp (tổng hợp)/sắp xếp lại các số từ KHỐI2 để làm cho nó như tương tự như KHỐI1 càng tốt. Tôi xác định sự tương tự như tổng các độ lệch ở mọi vị trí. Xem this post cho cách tôi tính tương tự. Số tiền càng nhỏ thì càng tốt.

Cách tiếp cận đầu tiên của tôi là thử tất cả các kết hợp và chọn kết hợp tốt nhất. Điều này chỉ hoạt động cho các bộ khá nhỏ (đặc biệt là nhóm thứ hai). Xem this post và câu trả lời từ Rawling. Có cách nào thông minh hơn để có được sự kết hợp tốt không? Tôi chắc chắn không cần cái tốt nhất. Một kết quả tốt sẽ là kết quả tốt. Rõ ràng là một tập hợp với các tập con rỗng là vô nghĩa. Các bộ không cân bằng cực kỳ không có vẻ rất hứa hẹn với tôi. SET1 có xu hướng có khoảng 8 nhưng có thể có tối đa 18 mục. SET2 thường có số lượng hơn 10 (tối đa 35). Tổng các số trong hai bộ là bằng nhau (ngoại trừ các lỗi làm tròn).

Dưới đây là một ví dụ với kết quả tốt và xấu (không phải tất cả những người có thể):

SET1 = { 272370, 194560, 233430 }; SET2 = { 53407.13, 100000, 365634.03, 181319.07 } 

     272370   |  194560   |  233430 
--------------------------------------------------------------------- 
    365634.03   | 100000 + 53407.13 |  181319.07  (best match) 
    365634.03   |  181319.07  | 100000 + 53407.13 (good) 
    365634.03   |  100000   |181319.07 + 53407.13 (ok) 
     53407.13   |365634.03 + 100000 |  181319.07  (bad) 
     53407.13   |365634.03 + 181319.07 |  100000  (bad) 
.     |365634.03 + 181319.07 | 53407.13 + 100000 (invalid) 
53407.13 + 100000 |365634.03 + 181319.07 |      (invalid) 

Xin vui lòng cho tôi biết nếu tôi quên để mô tả một tiền đề hoặc mô tả của tôi không rõ ràng hoặc thậm chí bị lỗi. Tôi cũng rất vui khi cung cấp một ví dụ khác.

Cảm ơn trước!

Answer 1

Heuristic, mà nên làm việc khá tốt:

1. list<int> set1, set2; 
2. sort(set2) // decreasing, set2[0] would be the greatest value in set2 
3. struct set1item = {set1index, value, list<int> chosen} 
4. prepare list<set1item> set1items from set1 //(index = index in set1 list, value = set1[index] and chosen = null) 
5. put set1items to some priorityqueue pq // ordered by value 
6. for each set2item in set2{ 
7.  item = pq.first() 
8.  item.chosen.add(set2item); 
9.  item.value -= set2item; 
10. pq.updateFirst(item) 
11.} 

Nó sẽ làm việc như: lặp qua set2 từ cao nhất đến thấp nhất, có yếu tố thực tế cao nhất từ ​​set1, giảm nó bằng yếu tố nhận được từ set2 và thêm yếu tố này từ set2 đến phần tử từ kết quả set1.

Bạn phải nhớ kiểm tra xem tất cả các phần tử từ set1 không có kết quả trống không.

Ví dụ1: Set1 = {20, 9, 7, 3}, Set2 = {7, 6, 6, 4, 2, 2, 2, 2, 2, 2, 2, 2}.

iter1: fromSet2 = 7, Set1 = {20:{}, 9:{}, 7:{}, 3:{}}, fromSet1=20. Giảm 20 xuống 7 và thêm 7 vào kết quả của nó. Cập nhật: Set1 = {13:{7}, 9:{}, 7:{}, 3:{}}.

iter2: fromSet2 = 6, Set1 = {13:{7}, 9:{}, 7:{}, 3:{}}, fromSet1=13. Giảm 13 xuống 6 và thêm 6 vào kết quả của nó. Cập nhật: Set1 = {7:{7, 6}, 9:{}, 7:{}, 3:{}}.

iter3: fromSet2 = 6, Set1 = {7:{7, 6}, 9:{}, 7:{}, 3:{}}, fromSet1=9. Giảm 9 xuống 6 và thêm 6 vào kết quả của nó. Cập nhật: Set1 = {7:{7, 6}, 3:{6}, 7:{}, 3:{}}.

iter4: fromSet2 = 4, Set1 = {7:{7, 6}, 3:{6}, 7:{}, 3:{}}, fromSet1=7. Giảm 7 xuống 4 và thêm 4 vào kết quả của nó. Cập nhật: Set1 = {3:{7, 6, 4}, 3:{6}, 7:{}, 3:{}}.

iter5: fromSet2 = 2, Set1 = {3:{7, 6, 4}, 3:{6}, 7:{}, 3:{}}, fromSet1=7. Giảm 7 xuống 2 và thêm 2 vào kết quả của nó. Đã cập nhật: Set1 = {3:{7, 6, 4}, 3:{6}, 5:{2}, 3:{}}.

...