Thuật toán - tìm phép trừ tối thiểu giữa tổng của hai mảng

Question

Tôi đang tìm việc và thực hiện nhiều bài tập thuật toán. Đây là vấn đề của tôi:

---

Với hai mảng: một và b với cùng một độ dài, vấn đề này là làm | sum (a) -sum (b) | tối thiểu, bằng cách hoán đổi các phần tử giữa a và b.

---

Dưới đây là mặc dù tôi:

giả sử chúng ta trao đổi a [i] và b [j], thiết lập Delt = sum (a) - sum (b), x = a [i] -b [j]
rồi Delt2 = tổng (a) -a [i] + b [j] - (tổng (b) -b [j] + a [i]) = Delt - 2 * x,
thì thay đổi = | Delt | - | Delt2 |, đó là tỷ lệ thuận với | Delt |^2 - | Delt2 |^2 = 4 * x * (Delt-x),

Dựa trên những suy nghĩ trên, chúng tôi nhận được đoạn mã sau:

---

Delt = sum(a) - sum(b); 
done = false; 
while(!done) 
{ 
    done = true; 
    for i = [0, n) 
    { 
     for j = [0,n) 
     { 
      x = a[i]-b[j]; 
      change = x*(Delt-x); 
      if(change >0) 
      { 
       swap(a[i], b[j]); 
       Delt = Delt - 2*x; 
       done = false; 
      } 
     } 
    } 
} 

---

Tuy nhiên, không ai có giải pháp tốt hơn? Nếu bạn có, xin vui lòng cho tôi biết và tôi sẽ rất biết ơn bạn!

Answer 1

Vấn đề này về cơ bản là vấn đề tối ưu hóa cho Partition Problem với sự hạn chế thêm của các phần bằng nhau. Tôi sẽ chứng minh rằng việc thêm ràng buộc này không làm cho vấn đề trở nên dễ dàng hơn.

NP-Hardness bằng chứng:
Giả sử có một thuật toán A rằng giải quyết vấn đề này trong thời gian đa thức, chúng ta có thể giải quyết vấn Partition-Problem trong thời gian đa thức.

Partition(S): 
for i in range(|S|): 
    S += {0} 
    result <- A(S\2,S\2) //arbitrary split S into 2 parts 
    if result is a partition: //simple to check, since partition is NP. 
    return true. 
return false //no partition 

đúng đắn:
Nếu có một phân vùng biểu thị như (S1, S2) [giả S2 có nhiều yếu tố], trên lặp | S2 | - | S1 | [I E. khi thêm | S2 | - | S1 | số không]. Đầu vào là A sẽ có đủ số không đủ để chúng ta có thể trả về hai mảng chiều dài bằng nhau: S2, S1 + {0,0, ..., 0}, sẽ là một phân vùng là S và thuật toán sẽ mang lại giá trị đúng.
Nếu thuật toán cho kết quả đúng và lặp lại k, chúng tôi có hai mảng: S2, S1, với cùng số lượng phần tử và giá trị bằng nhau. bằng cách loại bỏ k số không từ mảng, chúng tôi nhận được một phân vùng để S ban đầu, do đó, S đã có một phân vùng.

Đa thức:
giả A mất P(n) thời gian, thuật toán, chúng tôi sản xuất sẽ mất n*P(n) thời gian, cũng là đa thức.

Kết luận:
Nếu vấn đề này là solveable trong thời gian đa thức, thì Partion-Vấn đề, và do đó P = NP. dựa trên điều này: vấn đề này là NP-Hard.

Vì vấn đề này là NP-Hard, vì một giải pháp chính xác, bạn có thể sẽ cần một thuật toán số mũ. Một trong số đó là đơn giản backtracking [Tôi rời khỏi nó như là một bài tập cho người đọc để thực hiện một giải pháp quay lui]

EDIT: như đã đề cập bởi @jpalecek: bằng cách đơn giản tạo ra một giảm: S->S+(0,0,...,0) [k lần 0], một có thể trực tiếp chứng minh NP-Độ cứng bằng cách giảm. đa thức là tầm thường và chính xác là rất giống với bằng chứng chính xác của phần trên: [nếu có một phân vùng, thêm số không 'cân bằng' là có thể; hướng khác chỉ đơn giản là cắt tỉa những số 0]

Answer 2

Chỉ cần một nhận xét. Thông qua tất cả các trao đổi này bạn về cơ bản có thể sắp xếp các nội dung của cả hai mảng như bạn muốn. Vì vậy, nó không quan trọng trong đó mảng các giá trị được bắt đầu.

Không thể làm điều đó trong đầu của tôi nhưng tôi khá chắc chắn có một giải pháp xây dựng. Tôi nghĩ nếu bạn sắp xếp chúng đầu tiên và sau đó xử lý chúng theo một số quy tắc. Một số thứ dọc theo các dòng If value > 0 and if sum(a)>sum(b) then insert to a else into b