خوارزمية تقسم قائمة بالأرقام إلى 2 قوائم مجموع متساوية
https://stackoverflow.com/questions/890171
-
23-08-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russianسؤال
هناك قائمة بالأرقام.
سيتم تقسيم القائمة إلى 2 قوائم متساوية الحجم، مع الحد الأدنى من الفرق في المبلغ. يجب طباعة المبالغ.
#Example:
>>>que = [2,3,10,5,8,9,7,3,5,2]
>>>make_teams(que)
27 27
هل هناك خطأ في خوارزمية الكود التالية لبعض القضية؟
كيف يمكنني تحسين و / أو ثياب هذا؟
def make_teams(que):
que.sort()
if len(que)%2: que.insert(0,0)
t1,t2 = [],[]
while que:
val = (que.pop(), que.pop())
if sum(t1)>sum(t2):
t2.append(val[0])
t1.append(val[1])
else:
t1.append(val[0])
t2.append(val[1])
print min(sum(t1),sum(t2)), max(sum(t1),sum(t2)), "\n"
السؤال هو من http://www.codechef.com/problems/teamsel/
المحلول
حل جديد
هذا هو البحث الأول من الاتساع مع الاستدلال الداكن. تقتصر الشجرة على عمق اللاعبين / 2. حد مجموع اللاعب هو totalscores / 2. مع تجمع لاعب 100، استغرق الأمر حوالي 10 ثوان لحلها.
def team(t):
iterations = range(2, len(t)/2+1)
totalscore = sum(t)
halftotalscore = totalscore/2.0
oldmoves = {}
for p in t:
people_left = t[:]
people_left.remove(p)
oldmoves[p] = people_left
if iterations == []:
solution = min(map(lambda i: (abs(float(i)-halftotalscore), i), oldmoves.keys()))
return (solution[1], sum(oldmoves[solution[1]]), oldmoves[solution[1]])
for n in iterations:
newmoves = {}
for total, roster in oldmoves.iteritems():
for p in roster:
people_left = roster[:]
people_left.remove(p)
newtotal = total+p
if newtotal > halftotalscore: continue
newmoves[newtotal] = people_left
oldmoves = newmoves
solution = min(map(lambda i: (abs(float(i)-halftotalscore), i), oldmoves.keys()))
return (solution[1], sum(oldmoves[solution[1]]), oldmoves[solution[1]])
print team([90,200,100])
print team([2,3,10,5,8,9,7,3,5,2])
print team([1,1,1,1,1,1,1,1,1,9])
print team([87,100,28,67,68,41,67,1])
print team([1, 1, 50, 50, 50, 1000])
#output
#(200, 190, [90, 100])
#(27, 27, [3, 9, 7, 3, 5])
#(5, 13, [1, 1, 1, 1, 9])
#(229, 230, [28, 67, 68, 67])
#(150, 1002, [1, 1, 1000])
لاحظ أيضا أنني حاولت حل هذا باستخدام وصف GS، ولكن من المستحيل الحصول على معلومات كافية ببساطة عن طريق تخزين مجاميع التشغيل. وإذا كنت مخزن على حد سواء عدد العناصر والمجموعات، ثم سيكون هو نفسه مثل هذا الحل باستثناء البيانات التي لا داعي لها. لأنك تحتاج فقط إلى الحفاظ على التكرارات N-1 و N حتى Numplayers / 2.
كان لدي واحدة شاملة قديمة تعتمد على معاملات الحدية (انظر في التاريخ). حل مشاكل المثال الطول 10 على ما يرام، ولكن بعد ذلك رأيت أن المنافسة لديها أشخاص يصل طولها 100.
نصائح أخرى
البرمجة الديناميكية هو الحل الذي تبحث عنه.
مثال مع [4، 3، 10، 3، 2، 5]:
X-Axis: قابلة للوصول إلى مجموعة من المجموعة. MAX = SUM (جميع الأرقام) / 2 (تقريب) Y-Axis: عدد العناصر في المجموعة. أقصى = عدد الأرقام / 2 (تقريب) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 1 | | | | 4 | | | | | | | | | | | // 4 2 | | | | | | | | | | | | | | | 3 | | | | | | | | | | | | | | |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 1 | | | 3| 4| | | | | | | | | | | // 3 2 | | | | | | | 3| | | | | | | | 3 | | | | | | | | | | | | | | |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 1 | | | 3| 4| | | | | |10| | | | | // 10 2 | | | | | | | 3| | | | | |10|10| 3 | | | | | | | | | | | | | | |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 1 | | | 3| 4| | | | | |10| | | | | // 3 2 | | | | | | 3| 3| | | | | |10|10| 3 | | | | | | | | | | 3| | | | |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 1 | | 2| 3| 4| | | | | |10| | | | | // 2 2 | | | | | 2| 3| 3| | | | | 2|10|10| 3 | | | | | | | | 2| 2| 3| | | | |
1 2 3 4 5 6 7 8 9 10 11 12 13 14
1 | | 2| 3| 4| 5| | | | |10| | | | | // 5
2 | | | | | 2| 3| 3| 5| 5| | | 2|10|10|
3 | | | | | | | | 2| 2| 3| 5| 5| | |
^
12 هو رقم محظوظ لدينا! التراكين للحصول على المجموعة:
12 - 5 = 7 {5}
7 - 3 = 4 {5, 3}
4 - 4 = 0 {5, 3, 4}
يمكن بعد ذلك تحديد المجموعة الأخرى: {4،3،10،3،2،5} - {5،3،4} = {10،3،2}
جميع الحقول ذات الرقم هي حلول ممكنة لحقيبة واحدة. اختيار واحد أبعد في الزاوية اليمنى السفلى.
راجع للشغل: يطلق عليه napsack- مشكلة.
إذا كانت جميع الأوزان (W1، ...، WN و W) من الأعداد الصحيحة غير النظيفة، فيمكن حل مشكلة Neapsack في الوقت الزائدي متعدد الحدود باستخدام البرمجة الديناميكية.
حسنا، يمكنك العثور على حل لدقة النسبة المئوية في وقت متعدد الحدود، ولكن في الواقع العثور على الحل الأمثل (الحد الأدنى المطلق)، المشكلة هي NP-Complete. هذا يعني أنه لا يوجد حل زمني متعدد الحدود للمشكلة. نتيجة لذلك، حتى مع قائمة صغيرة نسبيا من الأرقام، فإنه يحسب مكثف للغاية لحلها. إذا كنت بحاجة حقا إلى حل، إلقاء نظرة على بعض خوارزميات التقريب لهذا.
س: بالنظر إلى أ multiset s من الأعداد الصحيحة, ، هل هناك طريقة للتقسيم اثنان مجموعتين S1 و S2 من هذا القبيل المجموع من الأرقام الموجودة في S1 يساوي مجموع الأرقام في S2؟
حظا سعيدا تقريب. :)
لاحظ أنه أيضا مزعج وانتقلت الفرز من الوظيفة.
def g(data):
sums = [0, 0]
for pair in zip(data[::2], data[1::2]):
item1, item2 = sorted(pair)
sums = sorted([sums[0] + item2, sums[1] + item1])
print sums
data = sorted([2,3,10,5,8,9,7,3,5,2])
g(data)
في الواقع التقسيم، حالة خاصة من الحمل.
هذا هو NP كاملة، مع خوارزميات DP الزائفة متعدد الحدود. يشير الزائفة في كثير الحدود الزائفة إلى حقيقة أن وقت التشغيل يعتمد على نطاق الأوزان.
بشكل عام، يجب أن تقرر أولا ما إذا كان هناك حل دقيق قبل أن تتمكن من قبول حل إرشادي.
حالة اختبار حيث لا تعمل طريقتك
que = [1, 1, 50, 50, 50, 1000]
المشكلة هي أنك تقوم بتحليل الأشياء في أزواج، وفي هذا المثال، تريد كل الخمسين في نفس المجموعة. يجب أن يتم حل ذلك رغم ذلك إذا قمت بإزالة جانب تحليل الزوج، فقم بإدخال إدخال واحد في كل مرة.
إليك الرمز الذي يفعل هذا
def make_teams(que):
que.sort()
que.reverse()
if len(que)%2: que.insert(0,0)
t1,t2 = [],[]
while que:
if abs(len(t1)-len(t2))>=len(que):
[t1, t2][len(t1)>len(t2)].append(que.pop(0))
else:
[t1, t2][sum(t1)>sum(t2)].append(que.pop(0))
print min(sum(t1),sum(t2)), max(sum(t1),sum(t2)), "\n"
if __name__=="__main__":
que = [2,3,10,5,8,9,7,3,5,2]
make_teams(que)
que = [1, 1, 50, 50, 50, 1000]
make_teams(que)
هذا يعطي 27 و 27 و 150، 1002 والتي هي الإجابات التي لها معنى لي.
يحرر: في مراجعة، أجد هذا لعدم عمله بالفعل، على الرغم من أنه في النهاية، لست متأكدا تماما عن السبب. سوف نشر رمز الاختبار الخاص بي هنا على الرغم من أنه قد يكون مفيدا. يولد الاختبار فقط تسلسل عشوائي يحتوي على مبالغ متساوية، ويضع هذه معا ويقارن (مع نتائج حزينة).
تحرير رقم 2: مقرها في المثال المدبب من قبل غير معروف، [87,100,28,67,68,41,67,1], من الواضح لماذا لا تعمل طريقتي. على وجه التحديد، لحل هذا المثال، يجب إضافة أكبر عدد ممكن من الأرقام إلى نفس التسلسل للحصول على حل صالح.
def make_sequence():
"""return the sums and the sequence that's devided to make this sum"""
while 1:
seq_len = randint(5, 200)
seq_max = [5, 10, 100, 1000, 1000000][randint(0,4)]
seqs = [[], []]
for i in range(seq_len):
for j in (0, 1):
seqs[j].append(randint(1, seq_max))
diff = sum(seqs[0])-sum(seqs[1])
if abs(diff)>=seq_max:
continue
if diff<0:
seqs[0][-1] += -diff
else:
seqs[1][-1] += diff
return sum(seqs[0]), sum(seqs[1]), seqs[0], seqs[1]
if __name__=="__main__":
for i in range(10):
s0, s1, seq0, seq1 = make_sequence()
t0, t1 = make_teams(seq0+seq1)
print s0, s1, t0, t1
if s0 != t0 or s1 != t1:
print "FAILURE", s0, s1, t0, t1
من الواضح أنهم يبحثون عن محلول نجيل البرمجة الديناميكي. لذلك بعد جهدي الأول (فكرت جهودي الأصلية جيدة جدا)، وجهد جهدي الثاني (حل حرم دقيق للغاية حقا يعمل على مجموعات بيانات قصيرة، وحتى لإعداد ما يصل إلى 100 عنصر طالما كان عدد فريدة من نوعها كانت القيم منخفضة)، استسلمت أخيرا لضغط الأقران وكتبت الشخص الذي يريدونه (ليس من الصعب التعامل مع الإدخالات المكررة كان هو الجزء الأكثر صعوبة - الخوارزمية الأساسية التي استنادتها إلى العمل فقط إذا كانت جميع المدخلات فريدة من نوعها - أنا متأكد سعدت ب طويل طويل هو كبير بما يكفي لعقد 50 بت!).
لذلك بالنسبة لجميع بيانات الاختبار وحالات الحافة المحرجة التي وضعتها معا أثناء اختبار جهودي الأولى، فإنها تعطي نفس الإجابة. على الأقل بالنسبة لتلك التي راجعت مع Solver التحريز، أنا أعرف انهم صحيحون. لكن ما زلت أفشل في التقديم مع بعض الإجابة الخاطئة!
أنا لا أطلب أي شخص إصلاح التعليمات البرمجية هنا، لكنني سأكون ممتن للغاية إذا كان بإمكان أي شخص العثور على القضية التي يولدها الكود أدناه الإجابة الخاطئة.
شكرا،
غراهام
PS هذا الرمز ينفذ دائما في غضون الحد الزمني ولكنه بعيد من الأمثل. أنا أبقيها بسيطة حتى يمر الاختبار، ثم لدي بعض الأفكار لتسريعها، ربما بعامل 10 أو أكثر.
#تتضمنu003Cstdio.h> # Define True (0 == 0) # Define False (0! = 0) Datic Int Debug = True؛ // int بسيط (const void * a، const void * b) {// return * (int *) a - * (int *) b؛ //} int الرئيسية (int argc، char ** argv) {int p [101]؛ Char * S، خط [128]؛ قناع طويل طويل، C0 [45001]، C1 [45001]؛ المهارة الدولية، اللاعبون، الهدف، أنا، J، الاختبارات، المجموع = 0؛ Debug = (Argc == 2 && Argv [1] [0] == '-' && Argv [1] [1] == 'D' && Argv [1] [2] == ' 0')؛ S = FENTS (خط، 127، Stdin)؛ اختبارات = ATOI (ق)؛ بينما (الاختبارات -> 0) {for (i = 0؛ i <45001؛ i ++) {c0 [i] = 0ll؛} s = fgets (خط، 127، stdin)؛ / * خط فارغ * / s = fgets (سطر، 127، ستودين)؛ / * عدد اللاعبين * / اللاعبين = ATOI (ق)؛ ل (i = 0؛ أنا <اللاعبين؛ i ++) {s = flects (خط، 127، stdin)؛ p [i] = atoi (s)؛} إذا (اللاعبون == 1) {printf ("0٪ d n"، p [0])؛ } آخر {إذا (اللاعبون و 1) ص [اللاعبين ++] = 0؛ // لاعب غريب ثابت عن طريق إضافة لاعب واحد من قوة 0 // qsort (p، اللاعبين، sizeof (int)، بسيطة)؛ المجموع = 0؛ ل (i = 0؛ أنا <اللاعبين؛ i ++) المجموع + = p [i]؛ الهدف = المجموع / 2؛ // حسنا إذا كان المجموع غريبة ونتيجة تقريب - فرق من قناع N، N + 1 = 1LL << (((((((طويل) للاعبين / 2ll) -1ll)؛ ل (i = 0؛ أنا <اللاعبين؛ i ++) {for (j = 0؛ j <= الهدف؛ j ++) {c1 [j] = 0ll؛} // memset سيكون مهارة أسرع = p [i]؛ // إضافة هذا المشغل إلى كل لاعب آخر وكل مجموعة فرعية جزئية ل (J = 0؛ J <= مهارة الهدف؛ J ++) {IF (C0 [J]) C1 [J + مهارة] = C0 [J] << 1 ؛ // أعلى = أعلى j + مهارة لتحسين لاحقا} c0 [مهارة] | = 1؛ // لذلك نحن لا نضيف رقم المهارة إلى حد ذاته إلا إذا حدث أكثر من مرة عن (J = 0؛ J <= الهدف؛ j ++) {c0 [j] | = c1 [j]؛} إذا (C0 [الهدف [الهدف [الهدف ] & قناع) استراحة. / / العودة المبكرة لملاءمة مثالية! } ل (i = الهدف؛ أنا> 0؛ I--) {IF (Debug || (C0 [i] & mask)) {fprintf (stdout، "٪ d٪ d n"، i، total-i) ؛ إذا (تصحيح) {IF (C0 [i] & mask) printf ("******** [")؛ طباعة أخرى ([")؛ ل (J = 0؛ j <= اللاعبين؛ j ++) إذا (c0 [i] & (1ll << طويل (طويل) J)) printf ("٪ d"، j + 1)؛ printf ("] n")؛ } كسر آخر؛ }}} إذا (اختبارات) printf (" n")؛ } إرجاع 0؛ }
class Team(object):
def __init__(self):
self.members = []
self.total = 0
def add(self, m):
self.members.append(m)
self.total += m
def __cmp__(self, other):
return cmp(self.total, other.total)
def make_teams(ns):
ns.sort(reverse = True)
t1, t2 = Team(), Team()
for n in ns:
t = t1 if t1 < t2 else t2
t.add(n)
return t1, t2
if __name__ == "__main__":
import sys
t1, t2 = make_teams([int(s) for s in sys.argv[1:]])
print t1.members, sum(t1.members)
print t2.members, sum(t2.members)
>python two_piles.py 1 50 50 100
[50, 50] 100
[100, 1] 101
للأداء، يمكنك حفظ الحسابات عن طريق استبدال التطبيق () ومجموع () مع مجاميع التشغيل.
يمكنك تشديد حلقاتك قليلا باستخدام ما يلي:
def make_teams(que):
que.sort()
t1, t2 = []
while que:
t1.append(que.pop())
if sum(t1) > sum(t2):
t2, t1 = t1, t2
print min(sum(t1),sum(t2)), max(sum(t1),sum(t2))
نظرا لأن القوائم يجب أن تساوي المشكلة ليست NP على الإطلاق.
قمت بتقسيم القائمة الفرز مع نمط T1 <- كوكي (1st، Last)، T2 <-que (2nd، Last-1) ...
def make_teams2(que):
que.sort()
if len(que)%2: que.insert(0,0)
t1 = []
t2 = []
while que:
if len(que) > 2:
t1.append(que.pop(0))
t1.append(que.pop())
t2.append(que.pop(0))
t2.append(que.pop())
else:
t1.append(que.pop(0))
t2.append(que.pop())
print sum(t1), sum(t2), "\n"
يحرر: أفترض أن هذه هي أيضا طريقة خاطئة. نتائج خاطئة!
بعد بعض التفكير، لعدم وجود مشكلة كبيرة جدا، أعتقد أن أفضل نوع من الاستدلال سيكون مثل:
import random
def f(data, nb_iter=20):
diff = None
sums = (None, None)
for _ in xrange(nb_iter):
random.shuffle(data)
mid = len(data)/2
sum1 = sum(data[:mid])
sum2 = sum(data[mid:])
if diff is None or abs(sum1 - sum2) < diff:
sums = (sum1, sum2)
print sums
يمكنك ضبط NB_ITER إذا كانت المشكلة أكبر.
إنه يحل كل المشكلة المذكورة أعلاه في الغالب طوال الوقت.
في تعليق سابق، افترضت أن المشكلة كما هي المجموعة كانت قابلة للاستمرار لأنها تختار بعناية بيانات الاختبار لتكون متوافقة مع خوارزميات مختلفة في غضون الوقت المخصص. ألا تكون هذه الحالة - بدلا من ذلك، فهي قيود المشكلة - الأرقام التي لا تزيد عن 450 و SET النهائي لا يزيد حجمها عن 50 رقما هو المفتاح. هذه متوافقة مع حل المشكلة باستخدام حل البرمجة الديناميكية التي طرحتها في منشور لاحق. لا يمكن لأي من الخوارزميات الأخرى (الاستدلال، أو التعداد الشامل من قبل مولد نمط الحركة الفردي) قد تعمل لأن هناك حالات اختبار كبيرة بما يكفي أو صعبة بما يكفي لكسر تلك الخوارزميات. إنه مزعج إلى حد ما أن نكون صادقين لأن تلك الحلول الأخرى أكثر صعوبة وبالتأكيد أكثر متعة. لاحظ أنه بدون الكثير من العمل الإضافي، يقول حل البرمجة الديناميكي فقط ما إذا كان الحل الممكن مع N / 2 لأي مبلغ معين، لكنه لا يخبرك بمحتويات أي قسم.
