בעיית הסכומים החלקיים – הבדלי גרסאות
תוכן שנמחק תוכן שנוסף
תגיות: עריכה ממכשיר נייד עריכה דרך האתר הנייד |
|||
שורה 49:
אם כל המספרים הם לא שליליים, ניתן לפתור זאת בזמן פולינומי ב-<math>n</math> וב-<math>\frac{1}{c}</math>.
נשים לב שבבעיה המקורית, אם כל סכום אפשרי של מספרים יכול להיכתב באמצעות P ביטים, אם נפתור את הבעיה המקורית באלגוריתם הקירוב עם <math>c=2^{-P}</math>, נפתור את הבעיה בדיוק. לכן אלגוריתם זה הוא פתרון מדויק של הבעיה כשהוא רץ בזמן פולינומי ב-<math>n</math> וב-<math>2^{P}</math> (כלומר, אקספוננציאלי ב
האלגוריתם המקורב לבעיה הוא:
|