Vấn đề về Bin-đóng gói (hoặc ba lô?)

Question

Tôi có bộ sưu tập từ 43 đến 50 số từ 0,33 đến 0,005 (nhưng chủ yếu ở phía nhỏ). Tôi muốn tìm, nếu có thể, tất cả các kết hợp mà có một khoản tiền giữa L và R, đó là rất gần nhau. *

Phương pháp brute-force mất 2 -2 bước, mà isn 't khả thi. Một phương pháp tốt để sử dụng ở đây là gì?

Chỉnh sửa: Các kết hợp sẽ được sử dụng để tính và loại bỏ. (Nếu bạn đang viết mã, bạn có thể giả sử chúng đơn giản là đầu ra; tôi sẽ sửa đổi khi cần.) Số lượng các kết hợp có lẽ sẽ quá lớn để giữ trong bộ nhớ.

* L = 0.5877866649021190081897311406, R = 0.5918521703507438353981412820.

Answer 1

Ý tưởng cơ bản là chuyển đổi nó thành một vấn đề ba lô số nguyên (dễ dàng).

Chọn số thực nhỏ e và số tròn trong vấn đề ban đầu của bạn với số có thể đại diện là k*e với số nguyên k. Các e nhỏ hơn, lớn hơn các số nguyên sẽ được (hiệu quả tradeoff) nhưng giải pháp của vấn đề sửa đổi sẽ được gần gũi hơn với bản gốc của bạn. An e=d/(4*43) trong đó d là chiều rộng của khoảng thời gian mục tiêu của bạn nên đủ nhỏ.

Nếu vấn đề đã sửa đổi có một giải pháp chính xác tổng hợp ở giữa (được làm tròn thành e) trong khoảng thời gian đích của bạn, thì vấn đề ban đầu có một nơi nào đó trong khoảng thời gian đó.

Answer 2

Bạn chưa cung cấp đủ thông tin cho chúng tôi. Nhưng có vẻ như bạn đang gặp rắc rối nếu bạn thực sự muốn OUTPUT mọi kết hợp có thể. Ví dụ, phù hợp với những gì bạn nói với chúng tôi là mỗi số là ~ .027. Nếu đây là trường hợp, thì mỗi bộ sưu tập của một nửa của các yếu tố với đáp ứng tiêu chí của bạn. Nhưng có 43 Chọn 21 bộ như vậy, có nghĩa là bạn phải xuất ít nhất 1052049481860 bộ. (quá nhiều để khả thi)

Chắc chắn thời gian chạy sẽ không tốt hơn độ dài của yêu cầu đầu ra.

Answer 3

Trên thực tế, có một cách nhanh hơn khoảng này:

(python)

sums_possible = [(0, [])] 
# sums_possible is an array of tuples like this: (number, numbers_that_yield_this_sum_array) 
for number in numbers: 
    sums_possible_for_this_number = [] 
    for sum in sums_possible: 
     sums_possible_for_this_number.insert((number + sum[0], sum[1] + [number])) 
    sums_possible = sums_possible + sums_possible_for_this_number 

results = [sum[1] for sum in sums_possible if sum[0]>=L and sum[1]<=R] 

Ngoài ra, Aaron là đúng, vì vậy điều này có thể hoặc không thể khả thi cho bạn