We prove that the greedy algorithm

We prove that the greedy algorithm uses the fewest possible trucks by showing that it “stays ahead” of any other solution. Specifically, we consider any other solution and show
the following. If the greedy algorithm fits boxes b1, b2, . . . , b into the first /c trucks, and the other solution fits b1, . . . , b into the first k trucks, then i < j. Note that this implies the optimality of the greedy algorithm, by setting k to be the number of trucks used by the
greedy algorithm.

ผลลัพธ์ (ไทย) 1:

เราพิสูจน์ว่า อัลกอริทึมตะกละใช้น้อยที่สุดได้รถบรรทุก โดยแสดงที่ว่า "อยู่ข้างหน้า" ของโซลูชันอื่น ๆ โดยเฉพาะ เราพิจารณาโซลูชันอื่น ๆ และแสดงต่อไปนี้ ถ้าอัลกอริทึมตะกละเหมาะกับกล่อง b1, b2,..., b เป็นรถบรรทุก /c แรก และโซลูชันเหมาะกับ b1,..., บีเป็นแรก k รถบรรทุก แล้วฉัน < เจ.หมายเหตุที่ว่า นี้หมายถึง optimality ของอัลกอริธึมที่ตะกละ ค่า k จำนวนรถบรรทุกที่ใช้ในอัลกอริทึมตะกละ

ผลลัพธ์ (ไทย) 2:

เราพิสูจน์ให้เห็นว่าขั้นตอนวิธีโลภใช้รถบรรทุกเป็นไปได้น้อยที่สุดโดยการแสดงให้เห็นว่ามัน "อยู่ข้างหน้า" ของการแก้ปัญหาอื่น ๆ โดยเฉพาะเราจะพิจารณาวิธีการแก้ปัญหาอื่น ๆ และแสดง
ต่อไปนี้ หากขั้นตอนวิธีโลภเหมาะกับกล่อง B1, B2, . . ขแรกที่เข้าไปในรถบรรทุก / C และวิธีการแก้ปัญหาอื่น ๆ ที่เหมาะกับ b1, . . ขเข้าไปในรถบรรทุก k แรกแล้ว i <ญ โปรดทราบว่านี้หมายถึง optimality ของขั้นตอนวิธีโลภโดยการตั้งค่า k เป็นหมายเลขของรถบรรทุกที่ใช้โดย
ขั้นตอนวิธีโลภ

ผลลัพธ์ (ไทย) 3:

เราพิสูจน์ได้ว่าอัลกอริทึมละโมบใช้รถบรรทุกที่เป็นไปได้น้อยที่สุด โดยเผยว่า " อยู่ข้างหน้า " ของอื่น ๆ โซลูชั่น โดยเฉพาะ เราพิจารณาโซลูชันอื่นและแสดง
ดังต่อไปนี้ ถ้าอัลกอริทึมละโมบพอดีกล่อง B1 , B2 , . . . . . . . . , B ในรถบรรทุก 1 / C , และโซลูชั่นอื่น ๆเหมาะกับ B1 . . . . . . . . , B ในรถบรรทุก K แรกแล้วผม < Jโปรดทราบว่านี้หมายถึงคุณภาพของขั้นตอนวิธีโลภโดยการตั้งค่า K จะเป็นหมายเลขของรถบรรทุกที่ใช้โดย

อัลกอริทึมละโมบ