बिन-पैकिंग (या knapsack?) समस्या

Question

मेरे पास 0.133 से 0.005 तक (लेकिन ज्यादातर छोटी तरफ) 43 से 50 संख्याओं का संग्रह है। मैं, खोजने के लिए यदि संभव हो तो चाहते हैं, सभी संयोजनों एल और आर के बीच एक योग है, जो एक साथ बहुत करीब हैं। *

जानवर बल विधि, 2 2 को कदम उठा लेता है जो प्रतिसाद नहीं व्यवहार्य नहीं है यहां उपयोग करने के लिए एक अच्छी विधि क्या है?

संपादित करें: संयोजनों का उपयोग गणना और त्याग में किया जाएगा। (यदि आप कोड लिख रहे हैं, तो आप मान सकते हैं कि वे बस आउटपुट हैं; मैं आवश्यकतानुसार संशोधित करूंगा।) संयोजनों की संख्या स्मृति में पकड़ने के लिए संभवतः बहुत बड़ी होगी।

* एल = 0.5877866649021190081897311406, आर = 0.5918521703507438353981412820।

Answer 1

के लिए संभव नहीं हो सकता मूल विचार इसे एक पूर्णांक knapsack समस्या में परिवर्तित करना है (जो आसान है)।

एक छोटी वास्तविक संख्या e और अपनी मूल समस्या में गोल संख्या k*e के साथ पूर्णांक k के साथ प्रतिनिधित्व करने योग्य चुनें। छोटे e, पूर्णांक पूर्णांक (दक्षता व्यापार) होगा लेकिन संशोधित समस्या का समाधान आपके मूल के करीब होगा। एक e=d/(4*43) जहां डी आपके लक्ष्य अंतराल की चौड़ाई पर्याप्त छोटा होना चाहिए।

यदि संशोधित समस्या में आपके लक्षित अंतराल के मध्य (e से गोलाकार) के बीच एक सटीक समाधान है, तो मूल समस्या अंतराल के भीतर कहीं कहीं है।

Answer 2

आपने हमें पर्याप्त जानकारी नहीं दी है। लेकिन ऐसा लगता है कि यदि आप वास्तव में हर संभावित संयोजन को आउटपुट करना चाहते हैं तो आप परेशानी में हैं। उदाहरण के लिए, आपने जो बताया है उसके अनुरूप, ये है कि प्रत्येक नंबर ~ .027 है। यदि यह मामला है, तो आपके मानदंड को पूरा करने वाले तत्वों के आधे हिस्से का संग्रह। लेकिन 43 ऐसे 21 सेट हैं, जिसका मतलब है कि आपको कम से कम 1052049481860 सेट आउटपुट करना होगा। (व्यवहार्य होने के लिए बहुत से लोग)

निश्चित रूप से चलने का समय आवश्यक आउटपुट की लंबाई से बेहतर नहीं होगा।

Answer 3

वास्तव में, वहाँ इस के चारों ओर एक तेज तरीका है:

(अजगर)

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] 

इसके अलावा, हारून सही है, तो यह या आप