Với hai danh sách các số và danh sách tổng số (không có trong bất kỳ thứ tự cụ thể):Tìm tập hợp các cặp tương ứng với danh sách các khoản tiền
a = [1,2,3]
b = [4,5,6]
c = [6,7,8]
Làm thế nào tôi có thể tìm thấy tất cả các bộ cặp d
nơi d[k] = (a[i], b[j])
như vậy rằng c[k] = a[i] + b[j]
nơi các cặp được sử dụng từ a và b mà không cần thay thế? (Tất cả các danh sách có thể có bản sao)
d = [(1,5), (3,4), (2,6)]
d = [(2,4), (1,6), (3,5)]
Đối c = [7,7,7]
:
d = [(1,6), (2,5), (3,4)]
(1 trả lời bởi vì tất cả các hoán vị cơ bản là tương đương)
Tôi muốn làm điều này với danh sách dài ~ 500, do đó, một kết hợp ngây thơ/tìm kiếm backtracking là ra câu hỏi.
Bạn muốn một tập hợp các chuỗi ghép nối trong đó mỗi chuỗi trong tập hợp có tổng số khớp với chuỗi c? Ngoài ra, trong ví dụ đầu tiên, sẽ [(1,5), (1,6), (2,6)] - và nhiều hơn nữa - cũng được bao gồm? –
Không thay thế. Vấn đề tôi đang cố gắng giải quyết là mỗi danh sách đều có điểm số của sinh viên.Tôi có quyền truy cập vào từng danh sách và tổng của cả hai, nhưng muốn biết được tổng số điểm, các điểm phụ có thể là gì. Nếu nó làm cho vấn đề trở nên dễ giải quyết hơn (hoặc tăng cơ hội của một giải pháp duy nhất), tôi có quyền truy cập vào N của các danh sách này và có thể truy vấn cơ sở dữ liệu cho danh sách tổng số cho bất kỳ tập con nào của chúng. – georgeyiu
Vấn đề này được mô tả trong Wikipedia là [Kết hợp 3 chiều số] (http://en.wikipedia.org/wiki/Numerical_3-dimensional_matching). Nó là NP-hoàn thành. –