الگوریتم حریصانه: تفاوت میان نسخه‌ها

روش اثبات به این صورت است که دنباله تصمیمات اتخاذ شده در هر مرحله را در نظر گرفته، دنباله‌ای بهینه پیدا کرده که با دنباله ساخته شده یکسان باشد(منظور از دنباله بهینه، دنباله‌ای از کار‌هاست که جواب بهینه را به ما می‌دهد). برای پیدا کردن دنباله، ابتدا یک دنباله بهینه را درنظر گرفته، در هر مرحله یک دنباله شبیه‌تر به دنباله خودمان پیدا می‌کنیم که بهینه باشد و سرانجام دنباله‌ای که پیدا کردیم با دنباله ما یکسان می‌شود.

 

 

درواقع شباهت دو دنباله بزرگ‌ترین عددی مثل xxx است که xxx عضو اول ابتدای هر دو دنباله با هم یکسان باشد.