Greedy algorithms

Question 1

בעית התרמיל השברית

מה הקלט והפלט

Answer 1

קלט:
W משקל מירבי
n זוגות של מספרים
כאשר 
vi value of i'th item
wi weight of i'th item

פלט:
רשימה של מספרים 
x1,...,xn 
s.t. 
0<=xi<=1
sum xi*wi<=W

The sum xi*v is maximized

Question 2

אלגוריתם חמדן לפתרון בעית התרמיל השברי

Answer 2

1. עיבוד מוקדם:
   חישוב הערכים הסגוליים
   ri=vi/wi
   ומיון הפריטים בסדר יורד לפי הערכים הסוגליים
2. איתחול
   G=empty set
3. איטרציה
   נעבור על הפריט מהראשון לאחרון ובכל שלב נכניס ל
   G
   כמה שיותר מהפריט הנוכחי (לפי אילוץ המשקל)
4. סיום
   נעצור כאשר התרמיל מלא או כאשר הכנסו את כל הפריטים

Question 3

זמן ריצה של אלגוריתם חמדן לפתרון בעיית התרמיל השלם

Answer 3

O(nlogn)

Sorting - O(nlong)

Iteration - O(n)

Question 4

מהו הפתרון החמדן לבעית התרמיל השברי

Answer 4

Define index t to be the last index that adding the t’th+1 item is above the weight limit.

x1=x2=…=xt=1

xt+1 = [W-(sum weight until t)]/w(t+1)

x(t+2)=…=xn=0

Question 5

למת ההחלפה של התרמיל השברי

Answer 5

Let Y=y1,y2,…,yn be a legal solution for the problem. Assume that there exists an index j, 1<=j<=n such that:

1. yj<1 (not all the j item was chosen)
2. Sum_i_1_to_j: yiwi