Tìm một tập hợp con mà đáp ứng một điều kiện nhất định

Question

Tôi có một vài mảng các số (mỗi phần tử của mảng chỉ có thể đưa giá trị 0 hoặc 1) như thế này

 
v1: 1; 0; 0; 1; 1; 
v2: 0; 1; 0; 0; 1; 
v3: 1; 1; 0; 1; 0; 
v4: 1; 0; 0; 1; 0; 
v5: 1; 1; 0; 1; 1; 
v6: 1; 1; 0; 1; 1; 

Tôi muốn tìm các tập con như vậy mà, khi mảng được tổng kết, mảng kết quả có các phần tử riêng lẻ là bội số của 2. Ví dụ, v1 + v2 + v3 cho một mảng kết quả là 2, 2, 0, 2, 2. Mảng kết quả có thể có bất kỳ giá trị nào bội số của 2.

Ví dụ khác:

 
v1: 1, 1, 1, 0, 1, 0 
v2: 0, 0, 1, 0, 0, 0 
v3: 1, 0, 0, 0, 0, 0 
v4: 0, 0, 0, 1, 0, 0 
v5: 1, 1, 0, 0, 1, 0 
v6: 0, 0, 1, 1, 0, 0 
v7: 1, 0, 1, 1, 0, 0 

Trong ví dụ này, v1 + v2 + v5 và v3 + v6 + v7 là các câu trả lời phù hợp.

Tôi có giải pháp về sức mạnh vũ phu, nhưng tôi muốn kiểm tra xem có phương pháp hiệu quả hơn hay không. Điều này có tương đương với vấn đề tổng hợp tập hợp con không?

Answer 1

Bạn có muốn tìm tất cả các giải pháp hay không?

Điều này có thể tìm thấy một giải pháp (và tôi nghĩ rằng có thể mở rộng nó để tìm tất cả các giải pháp).

Trình bày mỗi mảng dưới dạng số nhị phân.

Vì vậy, v1 trở thành 10011, v2 trở thành 01001, v.v.

Hãy để * biểu thị bitwise mod 2 bổ sung.

ví dụ:

v1*v2*v3 = 00000 

Vì vậy, mục tiêu của chúng tôi là tìm các mảng có bổ sung mod 2 là tất cả các số không. Cho u và v là bất kỳ số nhị phân nào. Sau đó, u * v = 0 iff u = v.

ví dụ:

(v1*v2)*v3 = 0 
v1*v2 = 11010 = v3. 

Ngoài ra nếu u * v = w sau đó

u*v*v = w*v, so 
u*0 = w*v, 
u = w*v 

Vì vậy, chúng ta có thể thực hiện tìm kiếm ngược lại bắt đầu từ 0. Giả sử tập cuối cùng của mảng chứa v. Sau đó, v * T = 0, nơi T là một số nhị phân. Chúng ta có T = 0 * v. Nếu T là một trong các mảng đã cho thì chúng ta đã hoàn thành. Nếu không, chúng tôi tiếp tục tìm kiếm bắt đầu từ T.

Điều này được mô tả chính thức bên dưới.

Mỗi trạng thái là số nhị phân.

Cho 0 là trạng thái ban đầu.

Các mảng đã cho một số tập hợp con của không gian trạng thái, nói S.

trạng thái mục tiêu của chúng tôi là bất kỳ yếu tố trong S.

Gọi T là tập hợp con yêu cầu của mảng có tổng là 0.

Ở mỗi trạng thái, hãy cho phép các hành động có thể * với bất kỳ trạng thái nào không nằm trong T.

Sau mỗi hành động đặt mảng được sử dụng trong T.

Nếu S = T ở bất kỳ giai đoạn không mục tiêu nào, thì không có giải pháp.

Bây giờ chúng tôi có thể chạy DFS trên không gian này để tìm giải pháp.