הבדלים בין גרסאות בדף "בעיית הסכומים החלקיים"

מ
פתרון בזמן פסאודו פולינומי אומר שעבור בעיה זהה בה הקלט הוא ב[[בסיס אונרי]] קיים פתרון הרץ בזמן פולינומי.
 
הפתרון לבעיה הזו משתמש ב[[תכנון דינמי]]. נניח שהקלט הוא מהצורה <math>X_1 , ... , X_n</math>, ועלינו לבדוק האם קיימת תת-קבוצה שסכום איבריה הוא אפס. יהא <math>A</math> הסכום של כל האיברים השליליים בקבוצה, ויהא <math>B</math> הסכום של כל האיברים החיוביים בה.
 
נגדיר את הפעולה הבוליאנית <math>Q(i,s)</math> להיות התשובה לשאלה: "האם קיימת תת-קבוצה של <math>X_1 , ... , X_i</math> שסכום איבריה הוא <math>s</math> ?". ברור כעת כי פתרון הבעיה הוא <math>Q(n,0)</math>.
 
נבחין כי עבור <math>A>s,s>B</math> מתקיים <math>\forall i: Q(i,s)=false</math>. כעת, ניצור טבלה בגודל <math>n * (B-A)</math>, כאשר הערך בנקודה <math>(i,j)</math> יהיההוא <math>Q(i,A+j)</math>, ונמלא את הטבלה מלמטה למעלה ומשמאל לימין באמצעות הרקורסיה הבאה:
 
* מקרה הבסיס: <math>Q(1,s) := (x_{1}==s)</math>
מילוי כל תא לוקח זמן <math>O(1)</math> כי ערכי הטבלה שהוא משתמש בהן בפסוק הלוגי ידועים כבר מחישובים קודמים, ולכן זמן מילוי הטבלה יהיה <math>O(n*(B-A))</math>.
 
הפתרון לא נחשב פולינומי בתורת הסיבוכיות כיוון שהערך <math>B-A</math> אינו פולינומי בגודל הבעיה, שהוא מספר הביטים שדרוש כדי לייצג אותם. האלגוריתם הוא פולינומי בערכים של <math>A</math> ושל <math>B</math>, שהם אקספוננציאלים במספר הביטים שלהם.
 
===אלגוריתם קירוב בזמן פולינומי===
627

עריכות