מבחן 07.07.12 שאלה 5
asaf (guest) 03 Jul 2013 15:41
you get 1<= A1 <… <An<=2n, and a numbre M, describe algorithms to count how many solution to the equetion
A1X1+…AnXn=M, each Xi= 0 or 1 or 2.
לדעתי זה תכנות דינאמי, הגדרתי פונקציה (שמייצגת את מספר הפתרונות למשוואה), היא מקבלת אינדקס התחלה לחישוב, ויעד לחישוב , נתחיל לחשב כשיש איבר אחד , ונוריד אינדקס במס' איברים
אבל לא היה ברור לי מה הסיבוכיות
destination: f(1,m)
recurtion: for j>0, i< n: f(i,j)= f(i+1,j)+ f(i+1,j-Ai)+ f(i+1,j-2Ai)
start solution: if j= 0, An or 2An, f(n,j)=1, else 0.
את הערכים נשמור במטריצה שאופסה לפני בגודל n*m
