יש לי שאלה שאני מצליח להתגבר עליה .

[ELIELI22]

יש לי שאלה שאני מצליח להתגבר עליה .

יש לי שאלה שאני מצליח להתגבר עליה אני אשמח אם אוכל לקבל עזרה . הבעיה היא בעיה דומה לבעית תרמיל הגב , דומה subset sums אבל כאן צריך פשוט לבנות איזושהי מטריצה בינארית ? (אולי) שמחשבת את התשובה (כמה סדרות מתאימות כאלו יש), אני לא הולך לישון עד שלא אסיים , אז אשמח לעזרה . נתונה קבוצה A = {a1, a2, a3,..., an} של מספרים שלמים וחיוביים ומספר נוסף k. נסמן ב-S איזושהי תת-קבוצה של A. ברצוננו למצוא את מספר התת-קבוצות של A, שעבורן מתקיים התנאי הבא: . לדוגמה: עבורA = {7, 4, 6, 1, 2} ו- 7 k =, קיימות שלוש תת-קבוצות של A שסכומן 7: {7}, {6, 1} ו-{4, 1, 2}. א. כתבו אלגוריתם תכנון דינמי לפתרון הבעיה. הדרכה: האלגוריתם צריך לבנות טבלה בגודל (n + 1)  (k + 1), כשהתשובה המבוקשת תימצא בתא (n, k) בטבלה. ב. ציירו את הטבלה המתקבלת עבור הדוגמה לעיל.

 

[ELIELI22]

לא מצליח כמובן .

 

[ELIELI22]

הצלחתי לכתוב תוכנית בC שמריצה את מה

הצלחתי לכתוב תוכנית בC שמריצה את מה שאני רוצה . עכשיו נותרתי עם שאלה מתמטית: התוכנית שלי יודעת עבור כל סידור של הקבוצה למצוא תת קבוצה מתאימה . האם יש דרך חוץ מלתת לתוכנית ב N! להריץ את כל הסידורים של המספרים בקבוצה . למצוא מהו מספר התת קבוצות . התוכנית : #include <stdio.h> #define I 6 // the number of numbers in ower group #define J 8 #define FALSE 0 #define TRUE 1 void main() { int C[J]; int W={0,2,4,6,1,7}; int j,i,w=J-1; // the sum we are lookin for is w int a=0; int sum=0; for (i=0;i<I;i++) C[0]=TRUE; for (j=1;j<=J-1;j++) C[0][j]=FALSE; for (i=1;i<=I-1;i++) { for (j=1;j<=w;j++) { C[j]=(C[i-1][j]==TRUE)||((j-W>=0)&&(C[i-1][j-W]==TRUE)); } } for (i=0;i<I;i++)//print the matrix { for (j=0;j<=w;j++) { int temp; temp=C[j]; printf("%d\t",temp); // print number } printf("**\n"); } i=I-1; j=J-1; while(C[I-1][J-1]==FALSE) j=j-1; while ((i>0)&&(j>0)) { //printf("i=%d,j=%d \t",i,j); if (C[j]==C[i-1][j]) i=i-1; else { printf("we took %d \t",W);//numbers we took . j=j-W; i=i-1; } } scanf("%d",&a); }

 

[Fingertip]

מה התנאי?

שסכום המספרים בכל קבוצה יהיה שווה ל-7? הטבלה כאמור תהיה בגודל n+1 x k+1, והתאים יהיו ממוספרים מ-0 עד k+1,n+1 בהתאמה. הערך בתא ixj, i≤n, j≤k יהיה מספר התת קבוצות של הקבוצה:

{a1, ..., ai}​

שסכום אבריהן הוא k בדיוק. אתה רואה איך אפשר להמשיך מכאן? אהד.

 

[ELIELI22]

קודם כל תודה. ואני חושב שיש לי קצה

אולי מישהו יכול לעזור לי בתרגום המשפט ל-C : או לפחות להזיר לי מה V ו^ שוים אני כבר לא זוכר .

 

[Fingertip]

זה צריך להיות משהו כזה

A[j] = A[i-1][j] || ((j - w >= 0) && A[i-1][j-w] )​

מקווה שעזרתי, אהד.

 

[ELIELI22]

האלגוריתם שלי עובד ...

עכשיו מה עושים ?? אני יודע שאלגוריתם שלי לפי הסדר של האיברים בקבוצה S ימצא תת סכום ששוה ל K . שאלה האם אני צריך לסדר את האיברים ב N! סידורים שונים (יש N איברים שונים בS) בכדי לקבל פיזית את כל הקבוצות המתאימות ?? או שאפשר להתחכם פה ? אשמח לעזרה.

 

[ELIELI22]

בסך הכל אני לא צריך לדעת מה התת קבו

בסך הכל אני לא צריך לדעת מה התת קבוצות אלא כמה כאלו יש .

 

[ELIELI22]

תודה.

 

[ELIELI22]

איך זה שונה מהאלגוריתם למציאת קבוצה

איך זה שונה מהאלגוריתם למציאת קבוצה אחת?

 

[ELIELI22]

עליתי על הרעיון , יש !!יש !!יש !!

אני כותב תוכנית בC אני אעלה אותה לאתר למי שיהיה מעונין . יצא עשן .