katia (guest) 20 Jun 2011 11:56
You have a set of n integers each in the range 0 … K. Partition these integers into two subsets such that you minimize |S1 - S2|, where S1 and S2 denote the sums of the elements in each of the two subsets.
זו שאלה 7 באתר(אתר שיש לינק אליו באתר הקורס) על תכנות דינמית.
בפתרון שמוצג שם הזמן הינו KN^2.
חשבתי על פתרון עם זמן ריצה טוב יותר:
תחילה נמיין את המספרים כך שנקבל סדרה לא עולה של מס' ניתן לעשות זאת בזמן לינארי מכיוון שאילו מס' שלמים בתחום סגור.
נסמן את הסדרה הממוינת:X1…XN
(כאשר X1 זהו מס' הכי גדול שיש לנו)
נתחיל להוסיף את המספרים ל2 הקב' לפי החוקים הבאים:
נשמור שדה עבור כל קב', שאומר לנו מה הסכום העדכני של קבוצה בכל שלב:S1i, S2i
S2i-סכום של קבוצה שתיים כאשר חילקנו כבר את
i המס' הראשונים.
נסמן ב P:i
את ההפרש המינימלי כאשר חילקנו כבר את i
המס' הראשונים ל2 הקבוצות.
הנוסחה עבור Pi תיהיה:
P:i=min{|S1(i-1) +Xi-S2(i-1)|, |S2(i-1)+Xi-S1(i-1)|} linear time
ובכל שלב נעדכן את סכומי הקב' אנחנו מעוניינים כמובן ב P:N
הרעיון הוא שנתחיל להוסיף מס' גדולים תחילה. בכל שלב נוסיף את האיבר הבא לקבוצה עם סכום מינימאלי של איברים. מובטח לנו שההפרש הוא מינימלי בכל שלב מכיוון שאם יש חוסר איזון-לא נוכל לתקן אותו ע"י העברת איברים שכבר בקבוצה מכיוון שהם גדולים יותר מXi
ולכן רק יגדילו חוסר איזון.
האם הפתרון נכון?
