הצפנת תרמיל גב – הבדלי גרסאות

תוכן שנמחק תוכן שנוסף
שורה 17:
נניח ש-<math>n=6</math> ונתונה הסדרה:
:<math>M=\{2,3,4,9,14,23\}</math> והתרמיל <math>S=27</math>
אפשר לראות ב[[ניסוי וטעייה]] שהפתרון הוא [[תת-סדרה|תת-הסדרה]] <math>\{24,9,14\}</math> וקל לראות שזהו הפתרון היחיד במקרה זה. דרך אחרת להציג את הפתרון היא ה[[מרחב וקטורי|ווקטור]] <math>\mathbf{e}=(0,0,1,1,1,0)</math> (כלומר הוקטור מכיל אחדים בכניסות המתאימות לאיברים הנכללים בסכום התרמיל ובכל היתר אפסים).
 
אפשר לפתור את הבעיה ב[[כוח גס]], פשוט על ידי ניסוי כל האפשרויות של הווקטור <math>\mathbf{e}</math> עד למציאת הוקטור הנכון. סיבוכיות הפתרון היא מסדר גודל של <math>O(2^n)</math>, אולם אפשר לחתוך את סיבוכיות הפתרון בפקטור של חצי על ידי אלגוריתם ההתנגשות הבא.