רוטר - שאלה קלילה

יומן פעילות	לוח שנה	מבזקי חדשות	תקנון	RSS	כותרות	כותרות לפי תגובה	ניקוי קוקיז	IP	להורדת אפליקציה
eBay	AliExpress	GearBest	Amazon	Booking	Kiwi	SkyScanner	Trip Advisor

"שאלה קלילה"

גירסת הדפסה

קבוצות דיון פיתוח, תיכנות ובניית אתרים נושא #14320	מנהל סגן המנהל מפקח Winner צל"ש מומחה

אשכול מספר 14320

DLN
חבר מתאריך 20.4.07
15884 הודעות

19:53 22.09.07

שאלה קלילה

יש לכם תיק היכול להכיל 15 ק"ג
יש לכם 10 אבנים שלכל אבן יש משקל וערך כספי
צריך לבנות אלגוריתם שימצא את צירוף של אבנים שיכנס לתיק ויהיה בעל ערך כספי הכי גבוה
אני הרבה דרכים אבל אני מחפש איזה משהו מתוחכם

שתף

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

האשכול	מחבר	תאריך כתיבה	מספר
כבר קראתי את זה פה בנוגע לפרוייקט גאמ''א, לא?	idan192	22.09.07 20:44	1
לע אבל כמה שיותר מתוחכם ויעיל יותר טוב :)	DLN	22.09.07 21:04	2
הממ...בעיקרון בתכנות דינאמי זה הכי יעיל אני חושב	sHuMpI	23.09.07 20:47	3
פרט נמק והסבר :\|	DLN	23.09.07 22:51	4
בכמה מילים	Net_Boy	23.09.07 23:18	12
הממ...לאיזו בעיה יש פתרון שיעזור לך במקרים אחרים?	sHuMpI	24.09.07 09:50	18
אלגוריתמים גנריים לדוגמא	Net_Boy	24.09.07 10:50	19
יאללה חברה להפעיל ראשים :)	DLN	23.09.07 22:52	5
יש פה איזה משהו עם קומבינטוריקה	Limp Bizkit	23.09.07 22:54	6
חח ממ אין לי מושג מה זה אבל תודה :)	DLN	23.09.07 22:55	7
קומבינטוריקה :	Limp Bizkit	23.09.07 22:57	8
פשש יפה :)	DLN	23.09.07 23:04	9
אופסי :פ וכן התכוונתי לתאריך הזה D:	Limp Bizkit	23.09.07 23:08	10
מתי מילאת את השאלון?	DLN	23.09.07 23:20	14
עוד בחופש הגדול :\|	Limp Bizkit	23.09.07 23:22	15
על פי חוקי הקומבינטוריקה	sHuMpI	24.09.07 09:46	17
אתה משלים את מה שאמרתי :)	Limp Bizkit	24.09.07 21:52	29
DLN, אמרת שהשאלה קלילה.	IcqBoy	23.09.07 23:10	11
ממ	DLN	23.09.07 23:20	13
הדרכים אולי ''יעילות'',אבל לא תמיד יעבדו	Limp Bizkit	23.09.07 23:28	16
זה לא נכון בוא אני אסביר לך גם למה	Net_Boy	24.09.07 10:57	21
בגלל זה אמרתי שאני רוצה דרך אחרת :\| יותר מתוחכמת	DLN	24.09.07 14:29	22
חח רואה שזה קשה :)	IcqBoy	24.09.07 22:12	33
הפיתרון שלי	Net_Boy	24.09.07 10:55	20
ממ אתה יכול לפרט עוד קצת על הפתרון? וזה יהיה מצוין אם תעלה יישום :)	DLN	24.09.07 14:31	23
אני עכשיו כותב יישום :)	Net_Boy	24.09.07 17:24	24
לא הבנתי כ''כ	עידן_הכלי	24.09.07 19:50	25
מיד אני מעלה את הפיתרון אני רק רושם כמה הערות	Net_Boy	24.09.07 21:17	26
הפיתרון שלי לתרגיל	Net_Boy	24.09.07 21:32	27
קצת כבד אחי...	Limp Bizkit	24.09.07 21:50	28
מבחינת נפח זה יצא גדול	Net_Boy	24.09.07 21:53	30
ובגלל שביקשו הסבר לפיתרון אני אנסה פחות או יותר	Net_Boy	24.09.07 21:58	31
נחמד מאוד	Limp Bizkit	24.09.07 22:06	32
אם כבר מממשים בתכנון דינאמי אז הנה הדרך הנכונה	איש-האבוקות	24.09.07 22:18	34
יפה מאוד	Limp Bizkit	24.09.07 22:37	35
n זה מספר האבנים וs זה המשקל כן?	DLN	25.09.07 12:23	38
ממ יש מצב אתה מסביר לי את זה במילים :\| לא הבנתי מה עשית שם עם הp_cell	DLN	25.09.07 12:34	39
בקשר לשאלה הקודמת כן	איש-האבוקות	25.09.07 12:43	40
כע הבנתי :) מגניב	DLN	25.09.07 13:03	41
אבל אחי זה לא יוצא נכון :\| שים לב אם אתה מגביל ל6 קילו יוצא יותר :\|	DLN	25.09.07 22:26	44
איזה משקלים שמת כי עם המשקלים שהיו זה עובד לפחות אצלי	איש-האבוקות	26.09.07 14:10	52
אותו הדבר שאתה עשית, לא שיניתי כלום וזה יוצא 150... צריך לצאת 155	DLN	26.09.07 14:31	53
מוזר ביותר כי אצלי כשאני מקמפל בgcc זה עובד כמו שצריך	איש-האבוקות	27.09.07 09:51	57
באמת מוזר :\|	DLN	27.09.07 12:18	59
יש מצב שאתה שינית תפרמטר הלא נכון	איש-האבוקות	27.09.07 12:30	61
נופ :\| לא שיניתי כלום :\| קופי פייסט לתוך הVS	DLN	27.09.07 12:32	62
אז לא הבנתי מה הבעיה, זה מחשב הדרך ליצור את המשקל 9	איש-האבוקות	27.09.07 12:54	63
חחחחח למדתי את זה בתואר שלי (מדעי המחשב) תשובה יפה והכי נכונה	arielvol	24.09.07 23:29	36
הנה בסיבוכיות N LOG N	Net_Boy	25.09.07 00:07	37
רגע זה בעצם מה שאני אמרתי עם הרטיו לא? זה עובד תמיד?	DLN	25.09.07 22:38	45
אני חשבתי על משהו הרבה יותר מסובך ד''א, כנסו.	IcqBoy	25.09.07 21:26	42
לוקחים את השק עם היחס ערך למשקל הכי גבוה כמה פעמים שאפשר?	DLN	25.09.07 22:18	43
נראה לי שאתה צודק.	IcqBoy	25.09.07 22:44	46
אבל משהו מוזר לי :\| השיטה עם היחס עובדת יותר טוב מהשיטה הרשמית לפתרון	DLN	25.09.07 22:55	47
השיטה עם היחס היא שיטה רשמית לפיתרון	Net_Boy	26.09.07 00:22	48
חח מגניב :)	DLN	26.09.07 14:33	54
חשוב לציין שאת הבעייה המקורית היא לא תפתור.	IcqBoy	27.09.07 03:26	56
למה לא?	DLN	27.09.07 12:19	60
בגלל השארית ...	IcqBoy	27.09.07 18:14	64
אני די בטוח שלפי הגרסא הזו אפשר גם להכניס חלקים של שקים	DLN	27.09.07 18:44	65
נכון כי השקים צריכים להיות מספר שלם	Net_Boy	27.09.07 20:05	67
לא קשור, קחו דוגמא נוספת.	IcqBoy	28.09.07 06:27	68
בקיצור סביר להניח שbacktracking יביא פה את הפתרון האופטימלי בכל מצב	DLN	28.09.07 11:36	69
מישהו יכול לעזור לי עם זה אגב?	DLN	28.09.07 11:39	70
אם הבנתי נכון	איש-האבוקות	28.09.07 17:18	71
כן רק מה שעשית מסובך רצח :\|	DLN	28.09.07 17:30	72
דיון מדהים	Sn00py	26.09.07 08:17	49
הפתרון שהכי נראה לי הגיוני	TheBinary	26.09.07 11:10	50
כן , האתר שהעלתי אליו די מעפן , מוחק את הקבצים מהר :\|	Net_Boy	26.09.07 12:17	51
הפונקציה sort מבוססת על quicksort?	TheBinary	27.09.07 01:58	55
כן	Net_Boy	27.09.07 11:08	58
אופס לאמשנה	DLN	27.09.07 20:00	66
כדי לסיים ת'נושא הזה	DLN	09.10.07 12:59	73

idan192

20:44 22.09.07

1. כבר קראתי את זה פה בנוגע לפרוייקט גאמ''א, לא?
בתגובה להודעה מספר 0

יש דרישה לסיבוכיות?

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

DLN
חבר מתאריך 20.4.07
15884 הודעות

21:04 22.09.07

2. לע אבל כמה שיותר מתוחכם ויעיל יותר טוב :)
בתגובה להודעה מספר 1

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

sHuMpI

20:47 23.09.07

3. הממ...בעיקרון בתכנות דינאמי זה הכי יעיל אני חושב
בתגובה להודעה מספר 0

תקן אותי אם אני טועה...

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

DLN
חבר מתאריך 20.4.07
15884 הודעות

22:51 23.09.07

4. פרט נמק והסבר :|
בתגובה להודעה מספר 3

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

Net_Boy

חבר מתאריך 1.4.02
17151 הודעות, 1 פידבק

23:18 23.09.07

12. בכמה מילים
בתגובה להודעה מספר 4

תיכנות דינאמי מתאים לפיתרון בעייה ספיציפית בלעדית ולא יעזור לך במקרים אחרים.
ככה עושים אופטימיזציה מקסימלית.

לי אישית יש פיתרון אבל נחכה בינתיים לאחרים שיפתרו.

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

sHuMpI

09:50 24.09.07

18. הממ...לאיזו בעיה יש פתרון שיעזור לך במקרים אחרים?
בתגובה להודעה מספר 12

דרך אגב...כבר פתרתי בתכנות דינאמי...
זה לקח לי זמן הכנה o(מספר האיברים* המשקל)
וזמן השאילתה o(1)...

למישהו יש פיתרון יותר טוב?

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

Net_Boy

חבר מתאריך 1.4.02
17151 הודעות, 1 פידבק

10:50 24.09.07

19. אלגוריתמים גנריים לדוגמא
בתגובה להודעה מספר 18

מיון , חיפוש , הוספה , מחיקה
וכו'....
ע"עgeneric algorithms בגוגל עבור עוד

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

DLN
חבר מתאריך 20.4.07
15884 הודעות

22:52 23.09.07

5. יאללה חברה להפעיל ראשים :)
בתגובה להודעה מספר 0

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

Limp Bizkit
חבר מתאריך 2.9.02
3436 הודעות

22:54 23.09.07

6. יש פה איזה משהו עם קומבינטוריקה
בתגובה להודעה מספר 0

והערך הגבוה מבין כל האפשרויות המתאימות

העברתי את השאלה למורה שלי למתמטיקה (מרצה באוניברסיטה), נחכה לתשובה

Ask any racer, any real racer. It doesn't matter if you win by an inch or a mile; winning's
winning.

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

DLN
חבר מתאריך 20.4.07
15884 הודעות

22:55 23.09.07

7. חח ממ אין לי מושג מה זה אבל תודה :)
בתגובה להודעה מספר 6

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

Limp Bizkit
חבר מתאריך 2.9.02
3436 הודעות

22:57 23.09.07

8. קומבינטוריקה :
בתגובה להודעה מספר 7

ערכתי לאחרונה בתאריך 23.09.07 בשעה 22:58 בברכה, Limp Bizkit

קומבינטוריקה היא ענף במתמטיקה בדידה, העוסק בספירתם של עצמים בקבוצות סופיות המקיימות קריטריון מסוים, ובהחלטה האם קיימים עצמים "אופטימליים" בקבוצות כאלה.

על פי חוקי הקומבינטוריקה (וזה יישמע ממש הזוי), אתה יודע שיש יותר מטריליון דרכים לסדר 15 מספרים בשורה אחת ?

אני כיתה י'ב, אבל הבית ספר החליט להשקיע בנו בשנים האחרונות, והביא לנו מורה ממש ממש טוב, שהוא גם מרצה באוניברסיטה ומאמן נבחרת ישראל במתמטיקה

דרך אגב - גם לי יש מיונים לגאמא ב-10.9, עוד מישהו הולך ?

Ask any racer, any real racer. It doesn't matter if you win by an inch or a mile; winning's
winning.

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

DLN
חבר מתאריך 20.4.07
15884 הודעות

23:04 23.09.07

9. פשש יפה :)
בתגובה להודעה מספר 8

יש לי אחלה של מורה למתמ' אבל מרצה באוניברסיטה היא לא
ממ אני שלחתי את השאלון לפני 3 ימים (תאריך סופי ה20 כאילו)
ואני מניח שאתה מתכוון ל9.10 לא ל10.9 :|
נקווה

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

Limp Bizkit
חבר מתאריך 2.9.02
3436 הודעות

23:08 23.09.07

10. אופסי :פ וכן התכוונתי לתאריך הזה D:
בתגובה להודעה מספר 9

תתקשר לברר מה קורה איתך, אולי נהיה ביחד במבחנים ^^

Ask any racer, any real racer. It doesn't matter if you win by an inch or a mile; winning's
winning.

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

DLN
חבר מתאריך 20.4.07
15884 הודעות

23:20 23.09.07

14. מתי מילאת את השאלון?
בתגובה להודעה מספר 10

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

Limp Bizkit
חבר מתאריך 2.9.02
3436 הודעות

23:22 23.09.07

15. עוד בחופש הגדול :|
בתגובה להודעה מספר 14

Ask any racer, any real racer. It doesn't matter if you win by an inch or a mile; winning's
winning.

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

sHuMpI

09:46 24.09.07

17. על פי חוקי הקומבינטוריקה
בתגובה להודעה מספר 8

יש בסה"כ 15! דרכים לסדר 15 מספרים בשורה אחת...

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

Limp Bizkit
חבר מתאריך 2.9.02
3436 הודעות

21:52 24.09.07

29. אתה משלים את מה שאמרתי :)
בתגובה להודעה מספר 17

נשמע קצת הזוי, אבל בסה"כ יש 1,307,674,368,000 דרכים לסדר 15 מספרים בשורה אחת

Ask any racer, any real racer. It doesn't matter if you win by an inch or a mile; winning's
winning.

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

IcqBoy

23:10 23.09.07

11. DLN, אמרת שהשאלה קלילה.
בתגובה להודעה מספר 0

אולי תשתף אותנו באחת מדרכיך הרבות לפתירת השאלה?

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

DLN
חבר מתאריך 20.4.07
15884 הודעות

23:20 23.09.07

13. ממ
בתגובה להודעה מספר 11

ערכתי לאחרונה בתאריך 23.09.07 בשעה 23:21 בברכה, DLN

הדרכים שלי לא נשמעות הכי יעילות או תמיד עובדות
והאמת שלא ניסיתי אותם
אבל חשבתי כזה דבר
למיין את האבנים לפי ערך כספי, מהגבוה לנמוך
ואז פשוט להתחיל להכניס אבנים לפי הסדר
ואם אבן לא נכנסת, נגיד אבן של 2 ק"ג ויש 14, אז ממשיכים הלאה לאבנים הבאות
אבל הקטע פה שיכול להיות שמאבדים פה לפחות ק"ג אם יוצא רק 14 :|
דרך שנייה דומה היא לקחת את האבנים שיש להם את היחס הכי גבוה של ערך למשקל

ואני אומר שהיא קלילה כי פעם עבדנו בכיתה במחשבים א' על משהו מאוד דומה שאנלא ממש זוכר חח

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

Limp Bizkit
חבר מתאריך 2.9.02
3436 הודעות

23:28 23.09.07

16. הדרכים אולי ''יעילות'',אבל לא תמיד יעבדו
בתגובה להודעה מספר 13

בהתייחס לערכים שנמצאים באבנים.

אני משער שהאלגוריתם שאמורים לבנות אמור לפתור את הבעיה לכל ערך אפשרי שתכניס לתוכנית

Ask any racer, any real racer. It doesn't matter if you win by an inch or a mile; winning's
winning.

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

Net_Boy

חבר מתאריך 1.4.02
17151 הודעות, 1 פידבק

10:57 24.09.07

21. זה לא נכון בוא אני אסביר לך גם למה
בתגובה להודעה מספר 13

כי נניח שהאבן הראשונה יש לה ערך 40 והיא שוקלת 15 (אין שום דבר בשאלה ששולל את זה)

ואז האבן השנייה והשלישית והרביעית שוות 39 כל אחת ושוקלות 5 לדוגמא.
אז לפי האלגוריתם שלך זה יקח את האבן הראשונה וזהו זה יסיים.

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

DLN
חבר מתאריך 20.4.07
15884 הודעות

14:29 24.09.07

22. בגלל זה אמרתי שאני רוצה דרך אחרת :| יותר מתוחכמת
בתגובה להודעה מספר 21

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

IcqBoy

22:12 24.09.07

33. חח רואה שזה קשה :)
בתגובה להודעה מספר 22

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

Net_Boy

חבר מתאריך 1.4.02
17151 הודעות, 1 פידבק

10:55 24.09.07

20. הפיתרון שלי
בתגובה להודעה מספר 0

ערכתי לאחרונה בתאריך 24.09.07 בשעה 10:58 בברכה, Net_Boy

לחלק את האבנים לתתי קבוצות לפי מספר האיברים
כאשר שמחלקים בודקים כל פעם שהמשקל לא עולה על 15 יכול להיות שווה או קטן.
בסופו של דבר עוברים על התתי קבוצות ורואים את המקסימליים

אם תרצו אני יעלה לכם בערב פיתרון בC++

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

DLN
חבר מתאריך 20.4.07
15884 הודעות

14:31 24.09.07

23. ממ אתה יכול לפרט עוד קצת על הפתרון? וזה יהיה מצוין אם תעלה יישום :)
בתגובה להודעה מספר 20

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

Net_Boy

חבר מתאריך 1.4.02
17151 הודעות, 1 פידבק

17:24 24.09.07

24. אני עכשיו כותב יישום :)
בתגובה להודעה מספר 23

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

עידן_הכלי

19:50 24.09.07

25. לא הבנתי כ''כ
בתגובה להודעה מספר 20

איך יוצא לך מהאלגוריתם הזה את הצירוף שיביא את הכי הרבה ערך?

אתה מחלק פה לכמות מסויימת של איברים, ואתה לא בודק את כל הצירופים, יכול להיות צירוף שיביא יותר מכל הצירופים שניסית.

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

Net_Boy

חבר מתאריך 1.4.02
17151 הודעות, 1 פידבק

21:17 24.09.07

26. מיד אני מעלה את הפיתרון אני רק רושם כמה הערות
בתגובה להודעה מספר 25

שיהיה מובן

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

Net_Boy

חבר מתאריך 1.4.02
17151 הודעות, 1 פידבק

21:32 24.09.07

27. הפיתרון שלי לתרגיל
בתגובה להודעה מספר 26

זה קוד טיפה כבד אז אם מישהו לא מבין משהו שישאל ואני אסביר

http://rafb.net/p/XW0CAg35.html

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

Limp Bizkit
חבר מתאריך 2.9.02
3436 הודעות

21:50 24.09.07

28. קצת כבד אחי...
בתגובה להודעה מספר 27

אני בטוח שבמבחנים לגאמא לא יידרשו ממך לכתוב קוד כזה

בכל מקרה - אני אעבור על הקוד יותר מאוחר

Ask any racer, any real racer. It doesn't matter if you win by an inch or a mile; winning's
winning.

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

Net_Boy

חבר מתאריך 1.4.02
17151 הודעות, 1 פידבק

21:53 24.09.07

30. מבחינת נפח זה יצא גדול
בתגובה להודעה מספר 28

ערכתי לאחרונה בתאריך 24.09.07 בשעה 23:43 בברכה, Net_Boy

אבל זה כי עשיתי אופטימזציה לקבוצת החזקה של האבנים כדי להראות למי ששאל פה מתי בדיוק טוב dynamic programming וזה מקרה קלאסי.
בפועל הפיתרון הזה די יעיל אבל אך ורק לקלטים קטנים , בקלטים גדולים זה יקח זמן מטורףףףףףףףף

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

Net_Boy

חבר מתאריך 1.4.02
17151 הודעות, 1 פידבק

21:58 24.09.07

31. ובגלל שביקשו הסבר לפיתרון אני אנסה פחות או יותר
בתגובה להודעה מספר 30

ערכתי לאחרונה בתאריך 24.09.07 בשעה 22:00 בברכה, Net_Boy

אני נעזרתי במבנה SET שמייצג קבוצה
http://he.wikipedia.org/wiki/%D7%A7%D7%91%D7%95%D7%A6%D7%94_(%D7%9E%D7%AA%D7%9E%D7%98%D7%99%D7%A7%D7%94)
והשתמשתי במה שנקרא קבוצת החזקה שזה כל תתי הקבוצות של קבוצה מסוימת.
בפועל עבור N איברים בקבוצה יהיו בקבוצת החזקה 2 בחזקת N איברים.
את הפונקציה ליצירת קבוצת החזקה יצרתי כ template function
ועשיתי template specialization ל Stones שיצור תתי קבוצות רק אם המשקל הכולל שלהן הוא קטן או שווה ל 15.
לצורך העניין לפי הדוגמא עם המספרים האקראיים שלי במקום 1024 תתי קבוצות יש בסביבות ה40, לכן פה זה היה מאד חשוב לייעל.

ובסוף יצרתי פונקציית השוואה שפועלת על פי הערך הכולל של הקבוצה
והקבוצה עם הערך הגבוה ביותר מוצגת בסוף

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

Limp Bizkit
חבר מתאריך 2.9.02
3436 הודעות

22:06 24.09.07

32. נחמד מאוד
בתגובה להודעה מספר 31

אני העברתי את השאלה למורה שלי למתמטיקה (מרצה באוניברסיטה) על מנת לקבל פתרון יעיל

מחר נקבל תשובה ונמיר אותה למחשב

Ask any racer, any real racer. It doesn't matter if you win by an inch or a mile; winning's
winning.

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

איש-האבוקות

22:18 24.09.07

34. אם כבר מממשים בתכנון דינאמי אז הנה הדרך הנכונה
בתגובה להודעה מספר 0

ערכתי לאחרונה בתאריך 24.09.07 בשעה 22:24 בברכה, איש-האבוקות

https://rotter.name/User_files/nor/46f81c076a37a2a1.txt
לא מסובך מידי, זאת בעיה קלאסית בתכנון דינאמי והיא נקראת KNAPSACK
כתבתי תפתרון בעצמי בלי להעזר באלגוריתם לפתרון, רק אחריי שפתרתי מצאתי שיש לבעיה שם

שכחתי לציין שבתנאי השאלה התוכנית פותרת בסיבוכיות לינארית אך במקרה הכללי שהמשקל שהשק יכול לסחוב הוא לא קבוע הסיבוכיות היא
(O(n*w

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

Limp Bizkit
חבר מתאריך 2.9.02
3436 הודעות

22:37 24.09.07

35. יפה מאוד
בתגובה להודעה מספר 34

הנה עלינו על חיל המודיעין

Ask any racer, any real racer. It doesn't matter if you win by an inch or a mile; winning's
winning.

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

DLN
חבר מתאריך 20.4.07
15884 הודעות

12:23 25.09.07

38. n זה מספר האבנים וs זה המשקל כן?
בתגובה להודעה מספר 34

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

DLN
חבר מתאריך 20.4.07
15884 הודעות

12:34 25.09.07

39. ממ יש מצב אתה מסביר לי את זה במילים :| לא הבנתי מה עשית שם עם הp_cell
בתגובה להודעה מספר 38

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

איש-האבוקות

12:43 25.09.07

40. בקשר לשאלה הקודמת כן
בתגובה להודעה מספר 39

ובקשר לp_cell זאת פשוט בדיקה שהמשקל של המשקולת לא גדול יותר מהמשקל שנשאר כי אז הייתה חריגה מגבולות המערך במצב הזה p_cell פשוט שווה למספר 1- שהוא הערך הכי קטן שתא יכול לקבל כך שיתקבל הערך של התא השני כי הוא גדול או שווה ל 1-

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

DLN
חבר מתאריך 20.4.07
15884 הודעות

13:03 25.09.07

41. כע הבנתי :) מגניב
בתגובה להודעה מספר 40

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

DLN
חבר מתאריך 20.4.07
15884 הודעות

22:26 25.09.07

44. אבל אחי זה לא יוצא נכון :| שים לב אם אתה מגביל ל6 קילו יוצא יותר :|
בתגובה להודעה מספר 41

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

איש-האבוקות

14:10 26.09.07

52. איזה משקלים שמת כי עם המשקלים שהיו זה עובד לפחות אצלי
בתגובה להודעה מספר 44

ערכתי לאחרונה בתאריך 26.09.07 בשעה 14:17 בברכה, איש-האבוקות

תרשום תמשקלים כדיי שאני אוכל לבדוק

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

DLN
חבר מתאריך 20.4.07
15884 הודעות

14:31 26.09.07

53. אותו הדבר שאתה עשית, לא שיניתי כלום וזה יוצא 150... צריך לצאת 155
בתגובה להודעה מספר 52

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

איש-האבוקות

09:51 27.09.07

57. מוזר ביותר כי אצלי כשאני מקמפל בgcc זה עובד כמו שצריך
בתגובה להודעה מספר 53

אצלי זה מחזיר 155

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

DLN
חבר מתאריך 20.4.07
15884 הודעות

12:18 27.09.07

59. באמת מוזר :|
בתגובה להודעה מספר 57

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

איש-האבוקות

12:30 27.09.07

61. יש מצב שאתה שינית תפרמטר הלא נכון
בתגובה להודעה מספר 59

יכול להיות ששינית בטעות את ה-5 שהוא מספר המשקולות בטעות ל6 והשארת את ה-9 שהוא המשקל שיכול השק להכיל כי כך אני מקבל באמת בתא האחרון שהוא מדפיס 150 אבל אני אז מקבלים גם סיגמנסיין פואלט כי זה חורג מגבולות המערך

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

DLN
חבר מתאריך 20.4.07
15884 הודעות

12:32 27.09.07

62. נופ :| לא שיניתי כלום :| קופי פייסט לתוך הVS
בתגובה להודעה מספר 61

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

איש-האבוקות

12:54 27.09.07

63. אז לא הבנתי מה הבעיה, זה מחשב הדרך ליצור את המשקל 9
בתגובה להודעה מספר 62

ולא את המספר 6

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

arielvol
חבר מתאריך 18.3.02
851 הודעות

23:29 24.09.07

36. חחחחח למדתי את זה בתואר שלי (מדעי המחשב) תשובה יפה והכי נכונה
בתגובה להודעה מספר 0

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

Net_Boy

חבר מתאריך 1.4.02
17151 הודעות, 1 פידבק

00:07 25.09.07

37. הנה בסיבוכיות N LOG N
בתגובה להודעה מספר 0

ערכתי לאחרונה בתאריך 25.09.07 בשעה 00:08 בברכה, Net_Boy

הסיבוכיות היחידה פה היא של מיון מהיר , הכל נעשה על פי יחס וממוין מהגבוה לנמוך ובסופו של דבר ממלאים את התרמיל עד שהוא מתמלא , זה עובד

http://rafb.net/p/vhfWPW89.html

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

DLN
חבר מתאריך 20.4.07
15884 הודעות

22:38 25.09.07

45. רגע זה בעצם מה שאני אמרתי עם הרטיו לא? זה עובד תמיד?
בתגובה להודעה מספר 37

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

IcqBoy

21:26 25.09.07

42. אני חשבתי על משהו הרבה יותר מסובך ד''א, כנסו.
בתגובה להודעה מספר 0

בקו מחשבה שלי אמרתי שיש 10 שקים עם ערך כספי ומשקל אבל שאפשר להשתמש בכל אחד אינסוף פעמים ...
את זה אתם יכולים לפתור?

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

DLN
חבר מתאריך 20.4.07
15884 הודעות

22:18 25.09.07

43. לוקחים את השק עם היחס ערך למשקל הכי גבוה כמה פעמים שאפשר?
בתגובה להודעה מספר 42

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

IcqBoy

22:44 25.09.07

46. נראה לי שאתה צודק.
בתגובה להודעה מספר 43

ערכתי לאחרונה בתאריך 25.09.07 בשעה 22:44 בברכה, IcqBoy

נראה לי סוכם הנושא

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

DLN
חבר מתאריך 20.4.07
15884 הודעות

22:55 25.09.07

47. אבל משהו מוזר לי :| השיטה עם היחס עובדת יותר טוב מהשיטה הרשמית לפתרון
בתגובה להודעה מספר 46

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

Net_Boy

חבר מתאריך 1.4.02
17151 הודעות, 1 פידבק

00:22 26.09.07

48. השיטה עם היחס היא שיטה רשמית לפיתרון
בתגובה להודעה מספר 47

ונקראת
fractional knapsack

וזהו אני באמת חושב שמיצינו

נ.ב
ח"ח על היוזמה - מזמן לא היה לנו פה דיון של 50 עמודים

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

DLN
חבר מתאריך 20.4.07
15884 הודעות

14:33 26.09.07

54. חח מגניב :)
בתגובה להודעה מספר 48

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

IcqBoy

03:26 27.09.07

56. חשוב לציין שאת הבעייה המקורית היא לא תפתור.
בתגובה להודעה מספר 47

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

DLN
חבר מתאריך 20.4.07
15884 הודעות

12:19 27.09.07

60. למה לא?
בתגובה להודעה מספר 56

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

IcqBoy

18:14 27.09.07

64. בגלל השארית ...
בתגובה להודעה מספר 60

ערכתי לאחרונה בתאריך 27.09.07 בשעה 18:15 בברכה, IcqBoy

נגיד נשארת במצב כזה:
בתיק יש נגיד 10$ ומקום לעוד 2 קילו.
שק אחד: 1.5 קילו, 1.6$.
שק שני: 2 קילו, 2$.
היחס של שק אחד יותר גדול בין הכסף למשקל ולכן תכניס אותו - המצב אחרי ההכנסה יהיה:
מקום בתיק: 0.5 קילו.
כסף בתיק: 11.6$.

אין אפשרות להכניס עוד שקים ...
לו היית מכניס את השק השני כשהיה לך עוד מקום ל-2 קילו בתיק - על אף שבו יש יחס נמוך יותר - היית מקבל תוצאה של 12$ בתיק (עוד 0.4 דולר במקרה זה).

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

DLN
חבר מתאריך 20.4.07
15884 הודעות

18:44 27.09.07

65. אני די בטוח שלפי הגרסא הזו אפשר גם להכניס חלקים של שקים
בתגובה להודעה מספר 64

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

Net_Boy

חבר מתאריך 1.4.02
17151 הודעות, 1 פידבק

20:05 27.09.07

67. נכון כי השקים צריכים להיות מספר שלם
בתגובה להודעה מספר 65

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

IcqBoy

06:27 28.09.07

68. לא קשור, קחו דוגמא נוספת.
בתגובה להודעה מספר 67

שק 1 -
משקל: 3 קילו.
כסף: 5$.
יחס: 5/3
שק 2 -
משקל: 2 קילו.
כסף: 4$.
יחס: 2.
תיק:
משקל שנותר לאיחסון: 3 קילו.
עפ"י הצעת הפיתרון של DLN, נקח את השק עם היחס היותר גדול ונכניס לתיק את שק 2 השוקל 2 קילו בעל 4 דולרים. נותר איפוא 1 קילו בתיק. אין אפשרות עוד להכניס.
הפיתרון הנכון: הכנסת שק מספר 1 שמשקלו 3 קילו והכסף שבו הוא 5$. קח יהיה בתיק 0 קילו נותרים (לא שזה משנה מה) אבל 1$ יותר.

ומה זאת אומרת חלק מהשק ?! אי אפשר לשקול את המטבעות ! ואם זה מתיל זהב בכלל ...

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

DLN
חבר מתאריך 20.4.07
15884 הודעות

11:36 28.09.07

69. בקיצור סביר להניח שbacktracking יביא פה את הפתרון האופטימלי בכל מצב
בתגובה להודעה מספר 68

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

DLN
חבר מתאריך 20.4.07
15884 הודעות

11:39 28.09.07

70. מישהו יכול לעזור לי עם זה אגב?
בתגובה להודעה מספר 69

אנלא כל כך מבין איך אני יכול לבדוק את כל הצירופים :|
זתומרת נניח יש לי מערך של 5 תאים
איך אני גורם לו לעבור על כל התאים בצורת עץ
כלומר כל הצירופים האפשריים לתא ראשון (זה לא הכי בעיה)
כל הצירופים האפשריים לתא שני (איך אני אומר לו לחזור גם לתא הראשון :|)
וכו'
ואיך אני שולל צירופים זהים :|

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

איש-האבוקות

17:18 28.09.07

71. אם הבנתי נכון
בתגובה להודעה מספר 70

הפתרון למה שאתה מחפש הוא תכנון דינאמי וזה בדיוק הפתרון שאני כתבתי, בפתרון בבקטראקינג מחשבים את אותם הערכים פעמים רבות ולכן סדר הגודל מתנפח בצורה דרסטית ואז התכנון הדינאמי בא לעזרתך בכך שאתה מנצל את זה שפתרת את תת הבעיה הזאת קודם לכן ולא צריך לחשב אותה פעם נוספת כפי שקורא בדרך הרגילה עם בקטראקינג

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

DLN
חבר מתאריך 20.4.07
15884 הודעות

17:30 28.09.07

72. כן רק מה שעשית מסובך רצח :|
בתגובה להודעה מספר 71

לא לרמה שלי חח
לא הייתי חושב על זה והאמת שגם עכשיו אנלא מבין את זה 100 אחוז חח

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

Sn00py
חבר מתאריך 1.8.02
2954 הודעות

08:17 26.09.07

49. דיון מדהים
בתגובה להודעה מספר 0

\x6C\x65\x65\x74\x68\x61\x78\x30
\x72\x3A\x2D\x29
tresp4sser

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

TheBinary

11:10 26.09.07

50. הפתרון שהכי נראה לי הגיוני
בתגובה להודעה מספר 0

ערכתי לאחרונה בתאריך 26.09.07 בשעה 11:32 בברכה, TheBinary

זה רקורסיה עם backtracking.
לא כ"כ בעיה לבנות את זה,
אבל זה ממש לא יעיל.

עריכה: Net_Boy, אתה יכול להעלות את הפתרון שוב?

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

Net_Boy

חבר מתאריך 1.4.02
17151 הודעות, 1 פידבק

12:17 26.09.07

51. כן , האתר שהעלתי אליו די מעפן , מוחק את הקבצים מהר :|
בתגובה להודעה מספר 50

https://rotter.name/User_files/nor/46fa31a74f8dd6a1.txt

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

TheBinary

01:58 27.09.07

55. הפונקציה sort מבוססת על quicksort?
בתגובה להודעה מספר 51

אני לא ממש מתמצא במחלקות והספריות של C++ :|

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

Net_Boy

חבר מתאריך 1.4.02
17151 הודעות, 1 פידבק

11:08 27.09.07

58. כן
בתגובה להודעה מספר 55

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

DLN
חבר מתאריך 20.4.07
15884 הודעות

20:00 27.09.07

66. אופס לאמשנה
בתגובה להודעה מספר 50

ערכתי לאחרונה בתאריך 27.09.07 בשעה 20:12 בברכה, DLN

חח אני דפוק שכחתי לבדוק תנאים

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

DLN
חבר מתאריך 20.4.07
15884 הודעות

12:59 09.10.07

73. כדי לסיים ת'נושא הזה
בתגובה להודעה מספר 0

ערכתי לאחרונה בתאריך 09.10.07 בשעה 13:00 בברכה, DLN

הנה פתרון פשוט ברקורסיה שפועל למיטב ידיעתי בכל מצב.

#include "stdafx.h"
#include<conio.h>
#include<stdio.h>
#define n 6
#define MAX(x,y) ((x)>(y)?(x):(y))
struct stone
{
int v,w;
};
struct stone a[n];
int F(int i,int w)
{
if (i==n)
return 0;
if (a[i].w>w)
return F(i+1,w);
return MAX(F(i+1,w),a[i].v+F(i+1,w-a[i].w));
}
void main()
{

a[0].v=2;
a[0].w=6;
a[1].v=9;
a[1].w=6;
a[2].v=5;
a[2].w=3;
a[3].v=7;
a[3].w=2;
a[4].v=6;
a[4].w=3;
a[5].v=2;
a[5].w=3;
printf("%d\n",F(0,10));
getch();
}
}

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד