روش حریصانه(Greedy Approach)

روش حریصانه(Greedy Approach)

اسلاید 1: روش حریصانه(Greedy Approach)رویکردی که روش حریصانه برای حل مسائل بهینه‌سازی دارد شامل تصمیم‌گیری‌های پشت‌سرهم است که برای هر تصمیم‌گیری تنها از اطلاعات بدست آمده تا آن مرحله استفاده می‌کند.بنابراین اصطلاحا گفته می‌شود که تصمیم‌گیری بر اساس انتخاب‌هایی صورت می‌پذیرد که به صورت محلی بهینه هستند. در این رویکرد حل مساله امیدواریم تا به راه حل بهینه برسیم. اما ...این راه حل بهینه دربرخی موارد بدست نمی‌آید.در این رویکرد برای هر الگوریتم پیشنهادی باید نشان داده شود که پاسخ همواره در تمامی موارد بهینه است.2

اسلاید 2: روش حریصانه(Greedy Approach)مساله: می‌خواهیم باقی پول مشتری را با تعدادی سکه (اسکناس) پرداخت کنیمwhile ( تازمانیکه سکه‌های بیشتری وجود دارد و مساله هنوز حل نشده است){ بزرگترین سکه باقیمانده را بردار;//selection procedure If (اضافه کردن سکه سبب می‌شود مجموع سکه‌های برداشته‌شده از مبلغ بدهی بیشتر شود)//feasibility check از اون سکه صرفنظر کن; else سکه را اضافه کن; If (اگر مجموع سکه‌های برداشته شده با بدهی برابری می‌کند)//solution check مساله حل شده است;}3123

اسلاید 3: روش حریصانه(Greedy Approach)در حل مسائل با شیوه حریصانه هر تکرار از سه بخش تشکیل شده است:الف) روال انتخاب (selection procedure)ب) امکان‌سنجی (feasibility check)ج) بررسی راه‌حل (solution check)4

اسلاید 4: روش حریصانه(Greedy Approach)در حل مسائل با شیوه حریصانه هر تکرار از سه بخش تشکیل شده است:الف) روال انتخاب (selection procedure)با معیاری آیتم بعدی را انتخاب می‌کند تا به مجموعه راه‌حل اضافه شود.توجه شود که معیار انتخاب مسلما بر اساس اطلاعات تا هر مرحله است ...هرچند سعی می‌شود تا بهینه باشد ولی چون ...از اطلاعات فقط تا همان مرحله استفاده می‌کند گفته می‌شود که معیار بهینگی محلی است.ب) امکان‌سنجی (feasibility check)با اضافه شدن آیتم جدید به مجموعه پاسخ، کنترل می‌شود که آیا با تکمیل کردن این مجموعه می‌توان به پاسخ رسید یا خیرج) بررسی راه‌حلکنترل می‌شود که با بدست آمدن مجموعه جدید آیا پاسخ پیدا شده یا باید تکرار بعدی هم انجام شود.5

اسلاید 5: الف) درخت‌های پوشای کمینه(Minimum Spanning Trees)فرض کنید که در برنامه‌ریزی احداث جاده بین شهرها، می‌خواهیم تعدادی شهر را با جاده به هم وصل کنیم تا امکان رفتن از هر شهر به شهر دیگر با جاده‌های احداث شده ممکن باشد.چنانچه بحث محدودیت بودجه‌ای مطرح باشد، بنابراین در این برنامه‌ریزی می‌خواهیم حداقل جاده را از نظر طولی احداث کنیم.در ادامه به دنبال الگوریتمی هستیم که مسائلی از این قبیل را حل کند.6

اسلاید 6: الف) درخت‌های پوشای کمینهاگر ارتباط بین شهرها را با گراف نمایش دهیم ...گراف حاصل جهت‌دار (directed) نیست. چراکه با احداث یک جاده بین هر دو شهر امکان رفت‌وآمد از هر دو شهر در این جاده وجود دارد.به گراف بدون جهت‌داری متصل (connected) گفته می‌شود که ...مسیری بین هر دو جفت راس وجود داشته باشد.7

اسلاید 7: الف) درخت‌های پوشای کمینهچرخه ساده (simple cycle): ...در هر گراف بدون جهت، مسیری از یک راس به خودش است چنانچه ...حداقل شامل سه راس باشد و ...هیچ راس میانی تکراری نباشد. گراف فاقدچرخه (Acyclic): گرافی غیرجهت‌دار است که ...هیچ چرخه ساده‌ای در آن وجود نداشته باشد.درخت (Tree) گرافی است ...غیرجهت‌دار (undirected)،متصل (connected) و فاقد چرخه (acyclic)8

اسلاید 8: 9گراف متصل، غیرجهت‌دار و وزن‌داراگر (v4,v5) را حذف کنیم این گراف همچنان متصل می‌ماند.درختی پوشا برای گراف بالادرخت پوشای کمینه

اسلاید 9: الف) درخت‌های پوشای کمینهاین مساله به این صورت بیان می‌شود:حذف یال‌هایی از یک گرافِ ...متصلِوزن‌دارِغیرجهت‌دارتا زیرگرافی بدست آید تا ...همچنان تمامی راس‌ها متصل به هم باقی بمانند ومجموع وزن یال‌های باقی‌مانده کمینه گردد.10

اسلاید 10: الف) درخت‌های پوشای کمینهاین مساله می‌تواند کاربردهای متعدد مانند:ساخت جادهدر ایجاد شبکه‌های مخابراتیدر ایجاد شبکه‌های لوله‌گذاری و ...11

اسلاید 11: الف) درخت‌های پوشای کمینهبرای اینکه زیرگرافی شرایط گفته‌شده را داشته باشد حتما بایستی ...درخت باشد. چراکه ...اگر زیرگرافی این شرایط را داشته باشد و درخت نباشد، بنابراین در آن حداقل یک چرخه ساده وجود خواهد داشت که ...می‌توانیم یکی از یال‌های چرخه را حذف کنیم و گراف حاصل همچنان ...متصل با مجموع وزن یال‌های کمتر باقی بماند12

اسلاید 12: الف) درخت‌های پوشای کمینهتعریف: گراف بدون جهتِ G شامل ...مجموعه V از راس‌های G و همچنین ...مجموعه E شامل یالها (که به صورت دو راس نشان داده می‌شود) می‌باشد.13

اسلاید 13: الف) درخت‌های پوشای کمینهبه اعضای V با vi اشاره می‌کنیم و همچنین ...یال بین vi و vj را با ...(vi , vj ) نشان می‌دهیم.14

اسلاید 14: الف) درخت‌های پوشای کمینه15

اسلاید 15: الف) درخت‌های پوشای کمینهدرخت پوشای T برای G تعداد راس‌های یکسان V همانند راس‌های G داردولی ...مجموعه یال‌های آن (F)، زیر مجموعه E است. بنابراین درخت پوشا را می‌توانیم به صورت زیر نشان دهیم:T=(V, F)16

اسلاید 16: الف) درخت‌های پوشای کمینهالگوریتم حریصانه سطح بالاF = Ø // مجموعه یالها را با تهی مقدار دهی کنwhile (the instance is not solved){ select an edge according to locally optimal consideration;// روال انتخاب if (adding the edge to F does not create a cycle) add it; // امکان‌سنجی if (T = (V, F) is a spanning tree) // بررسی راه حل the instance is solved;}17123

اسلاید 17: الف) درخت‌های پوشای کمینه- الگوریتم Primeالگوریتم پرایم (Prime) با مجموعه تهی از F کار را شروع می‌کند.مجوعه Y در این الگوریتم شامل راس‌هایی خواهد بود که به درخت پوشای کمینه اضافه شده‌اند و در ابتدا Y با راس دلخواهی مثلا {v1} مقداردهی اولیه می‌شود.نزدیکترین راس به Y راسی است که (1) عضو V-Y است و همچنین ...(2) به راسی که عضو Y است متصل است و (3) این اتصال با راسی است که ...حداقل وزن را دارد.18

اسلاید 18: الف) درخت‌های پوشای کمینه- الگوریتم Primeدر گراف شکل بالا، v2 نزدیک‌ترین راس به Y، زمانیکه Y = {v1} می‌باشد.نزدیکترین راس به Y و یال مربوطه به F اضافه می‌شود.بنابراین در این حالت، v2 به Y و (v1, v2) به F افزوده می‌شود.این فرایند افزودن نزدیکتر راس تا زمانیکه ...Y==V شود ادامه می‌یابد.19

اسلاید 19: الف) درخت‌های پوشای کمینه- الگوریتم Prime20

اسلاید 20: الف) درخت‌های پوشای کمینه- الگوریتم Prime21

اسلاید 21: الف) درخت‌های پوشای کمینه- الگوریتم Prime22دو بردار nearest و distance را برای حل این مساله به صورت زیر تعریف می‌کنیم:nearest(i)، اندیس راسی در Y است که به vi نزدیک‌تر است.distance(i)، مقدار وزن یال متصل‌کننده vi به nearest(i) می‌باشد.

اسلاید 22: function WT=prim(WG) n=max(size(WG)); Inf=1000; WT=Inf*ones(n,n); for i=2:n nearest(i)=1; distance(i)=WG(1,i); end added=false(n,1); added(1)=true; distance(1)=Inf;23 for k=1:n-1 [minvalue,vnear]=min(distance); WT(nearest(vnear),vnear)=minvalue; WT(vnear,nearest(vnear))=minvalue; added(vnear)=true; distance(vnear)=Inf; %nearest and distance should be updated. for i=2:n if ~added(i) if WG(i,vnear)<distance(i) distance(i)=WG(i,vnear); nearest(i)=vnear; end end end endend123

اسلاید 23: الف) درخت‌های پوشای کمینه- الگوریتم Primeالگوریتم پرایم مسلما درخت پوشا ایجاد می‌کند.ولی آیا لزوما درخت ایجاد شده کمینه است؟به دلیل اینکه در هر گام نزدیکترین راس به Y انتخاب می‌شود، به نظر می‌رسد که درخت ایجاد شده باید کمینه باشد.در این الگوریتم‌ها نیاز است درستی کارکرد الگوریتم اثبات شود.هرچند الگوریتم حریصانه در مقایسه با دیگر الگوریتم‌ها ساده‌تر است ولی اثبات بهینگی آنها معمولا کار دشواری است.24

اسلاید 24: الف) درخت‌های پوشای کمینه- الگوریتم Kruskalدر این روش به ازای هر vi عضو V یک زیرمجموعه مجزا ایجاد می‌شود که تنها شامل یک راس است.سپس یال‌ها که از قبل به ترتیب صعودی مرتب شده‌اند به ترتیب وارسی می‌شوند.چنانچه یالی دو راس در دو مجموعه جدا از هم را به هم متصل کند ...یال مربوطه به F اضافه شده و دو مجموعه که دو راس آن توسط یال به هم متصل شده بودند با هم ادغام می‌شوند.این فرایند تازمانیکه تمامی زیرمجموعه‌ها در یک مجموعه ادغام شوند ادامه می‌یابد.25

اسلاید 25: الف) درخت‌های پوشای کمینه- الگوریتم Kruskal26

اسلاید 26: الف) درخت‌های پوشای کمینه- الگوریتم Kruskal27

اسلاید 27: الف) درخت‌های پوشای کمینه- الگوریتم Kruskal28

اسلاید 28: ب) الگوریتم Dijkstra برای کوتاه‌ترین مسیر تک مبدااین الگوریتم هم از همان رویکرد الگوریتم پرایم برای مساله درخت پوشای کمینه استفاده می‌کند.مجموعه Y با راسی که کوتاه‌ترین مسیرها تا آن قرار است محاسبه شود مقداردهی اولیه می‌شود.در ادامه این راس v1 درنظر گرفته می‌شود.مجموعه F را برابر با مجموعه یال‌های موجود در کوتاه‌ترین مسیر از v1 به بقیه رئوس درنظر می‌گیریم که ...در شروع با تهی مقداردهی اولیه می‌شود.سپس راس v که نزدیکترین راس به v1 است را انتخاب می‌کنیم ...راس v را به Y و یال <v1, v> به F اضافه می‌کنیم.یال <v1, v> مسلما کوتاه‌ترین مسیر از v1 به v است.29

اسلاید 29: ب) الگوریتم Dijkstra برای کوتاه‌ترین مسیر تک مبداسپس مسیرهای از v1 به راس‌های عضو V-Y چک می‌شود که تنها از راس‌های عضو Y به عنوان راس میانی استفاده می‌کنند.مسیری که با این رویکرد به دست می‌آید، کوتاه‌ترین مسیر است (که البته باید اثبات شود)راسی که در انتهای چنین مسیری قرار دارد به Y و ...یالی که آن راس را در انتهای مسیر قرار می‌دهد به F اضافه می‌شود.این فرایند مادامیکه ....Y برابر V شود ادامه می‌یابد.پس در انتها، F شامل ...یال‌های موجود در کوتاه‌ترین مسیر از v1 به بقیه رئوس خواهد بود.30

اسلاید 30: ب) الگوریتم Dijkstra برای کوتاه‌ترین مسیر تک مبدا31

اسلاید 31: ب) الگوریتم Dijkstra برای کوتاه‌ترین مسیر تک مبدا32

اسلاید 32: ب) الگوریتم Dijkstra برای کوتاه‌ترین مسیر تک مبدابرای نوشتن الگوریتم این مساله هم نیاز به تعریف تعدادی متغیر است:length[i] = طول کوتاه‌ترین مسیر محاسبه شده فعلی (تا هر تکرار در الگوریتم حریصانه) از v1 به vi که ...فقط از راس‌های عضو Y به عنوان راس میانی استفاده می‌کند.touch[i] = اندیس راس v در Y که ...یال <v, vi> آخرین یال در کوتاه‌ترین مسیر جاری از v1 به vi باشد که ...تنها از راس‌های عضو Y به عنوان راس میانی استفاده کرده است.33

اسلاید 33: function S=dijkstra(W,s) n=max(size(W)); Inf=1000; S=Inf*ones(1,n); for i=1:n touch(i)=s; length(i)=W(s,i); end Y=false(n,1); Y(s)=true; length(s)=Inf;34 for k=1:n [minvalue,vnear]=min(length); Y(vnear)=true; S(vnear)=minvalue;%length(vnear) for i=1:n if ~added(i) if length(vnear)+W(vnear,i)<length(i) length(i)=length(vnear)+W(vnear,i); touch(i)=vnear; end end end length(vnear)=Inf; endend

اسلاید 34: ج) زمان‌بندی (Scheduling)درنظر بگیرید که در یک آرایشگاه تعدادی مشتری در انتظار دریافت خدمات مختلفی مانند اصلاح ساده، اصلاح با شستشو، رنگ مو و ... باشند.هر خدمتی در آرایشگاه زمان یکسانی با بقیه خدمات ندارد و آرایشگر می‌داند که هر خدمتی چه مقدار به طول خواهد انجامید.در این جا هدف آن است تا مشتریان به ترتیبی سرویس بگیرند که مجموع کل زمان‌های صرف شده برای انتظار و سرویس گرفتن کمینه گردد.زمان‌بندی که هدف بالا را تامین کند، زمان‌بندی بهینه نامیده می‌شود.35

اسلاید 35: ج) زمان‌بندیاگر زمان سپری شده برای انتظار و سرویس‌گرفتن هر مشتری را زمان سیستم (time in the system) بنامیم ...مساله در اینجا کمینه کردن تمامی زمان‌های سیستم (total time in the system) می‌باشد.این مساله کاربردهای گسترده‌ای مانند ...زمان‌بندی دسترسی کاربران به دیسک به‌گونه‌ایکه کل زمان سپری شده برای انتظار و سرویس‌گرفتن کمینه گردد.36

اسلاید 36: ج) زمان‌بندینوع دیگری از مساله زمان‌بندی وجود دارد که در آن ...هر کار (سرویس/مشتری) زمان یکسانی را برای انجام شدن نیاز دارند ولی ...هر کار مهلت (deadline) ای برای شروع شدن دارد که ...درصورتیکه شروع شود، منفعت (profit) مرتبط با آن حاصل می‌شود.در این مساله زمان‌بندی هدف آن است تا ...کارها به گونه‌ای زمان‌بندی شوند که بیشترین منفعت (total profit) بدست آید.بنابراین در ادامه ابتدا مساله زمان‌بندی بدون مهلت و سپس زمان‌بندی با مهلت ارائه خواهد گردید.37

اسلاید 37: ج) زمان‌بندی-کمینه‌سازی زمان کلفرض کنید سه کار و زمان پاسخ‌دهی به آنها به صورت زیر وجود دارد:اگر این سه کار به ترتیب 1 و 2 و 3 زمان‌بندی شوند، زمان سیستم هر کدام به صورت زیر می‌باشد:بنابراین تمامی زمان‌های سیستم به صورت زیر می‌باشد:38JobTime in the System15 (service time)25 (wait for job 1) + 10 (service time)35 (wait for job 1) + 10 (wait for job 2) + 4 (service time)

اسلاید 38: ج) زمان‌بندی-کمینه‌سازی زمان کلچنانچه تمامی زمان‌بندی‌های ممکن برای سه کار را ایجاد کنیم و برای هر ترتیب تمامی زمان‌های سیستم را محاسبه کنیم، جدول زیر به دست خواهد آمد:که زمان‌بندی [3, 1, 2] با تمامی زمان سیستم 32 بهینه خواهد بود.39Schedule Total Time in the System [1, 2, 3]5+(5+10)+(5+10+4) = 39[1, 3, 2]5+(5+4)+(5+4+10) = 33[2, 1, 3]10+(10+5)+(10+5+4) = 44[2, 3, 1]10+(10+4)+(10+4+5) = 43[3, 1, 2]4+(4+5)+(4+5+10) = 32[3, 2, 1]4+(4+10)+(4+10+5) = 37

اسلاید 39: ج) زمان‌بندی-کمینه‌سازی زمان کلواضح است الگوریتمی که به صورت brute force تمامی زمان‌بندی‌های ممکن را درنظر بگیرد دارای پیچیدگی محاسباتی ...فاکتوریل خواهد بود.همانگونه که مشخص است در مثال قبلی زمان‌بندی بهینه زمان حاصل شد که ...کار با کمترین زمان سرویس ابتدا انجام شد و پس از آن ....کار با زمان سرویس کمتر و ...چنین به نظر می‌رسد که چنین زمان‌بندی‌ای بهینه خواهد بود. 40

اسلاید 40: ج) زمان‌بندی-کمینه‌سازی زمان کلابتدا کارها را به ترتیب صعودی مرتب می‌کنیم و while ( the instance is not solved){ schedule the next job;// selection procedure and // feasibility check if ( there are no more jobs) // solution check the instance is solved; } 41

اسلاید 41: ج) زمان‌بندی-کمینه‌سازی زمان کلقضیه:تنها زمان‌بندی که سبب می‌شود کل زمان سیستم کمینه شود ...زمان‌بندی است که کارها به ترتیب صعودی سرویس داده شوند.42

اسلاید 42: ج) زمان‌بندی-کمینه‌سازی زمان کلاثبات: برای 1 ≤ i ≤ n − 1، ti را زمان سرویس برای iامین کار درنظر بگیرید که ...که در یک زمان‌بندی بهینه قرار دارد.می‌بایست نشان دهیم که در این زمان‌بندی ...کارها بر اساس زمان سرویسشان به ترتیب صعودی قرار گرفته‌اند.اثبات را با برهان خلف انجام می‌دهیم.43

اسلاید 43: ج) زمان‌بندی-کمینه‌سازی زمان کلچنانچه کارها کارهای به ترتیب صعودی مرتب نباشند آنگاه ...برای حداقل یک i، 1 ≤ i ≤ n − 1 خواهیم داشت ...44

اسلاید 44: ج) زمان‌بندی-کمینه‌سازی زمان کلمی‌توان ترتیب اولیه از کارها را با جابجا کردن کار iام و i+1 ام تغییر داد ...45

اسلاید 45: ج) زمان‌بندی-کمینه‌سازی زمان کلبنابراین اگر T برابر با کل زمان سیستم در زمان‌بندی اولیه باشد و T’ ...برابر با کل زمان‌بندی سیستم در ترتیب جدید باشد آنگاه خواهیم داشت ...و چون ti > ti+1پسکه فرض بهینه بودن زمان‌بندی اولیه را نقض می‌کند.46

اسلاید 46: ج) زمان‌بندی با مهلت معیندر این زما‌بندی هر کاری یک واحد زمان نیاز خواهد داشت تا به اتمام برسد.همچنین هر کاری یک مهلت و یک منفعت دارد.اگر کار قبل از مهلت و یا در زمان مهلتش آغاز شود در این صورت ...منفعتش برای سیستم حاصل خواهد شد.هدف این است تا کارهای به گونه‌ای زمان‌بندی شوند که بیشترین منفعت حاصل شود.در این زمان‌بندی الزامی وجود ندارد که تمامی کارها در زمان‌بندی وجود داشته باشند. همچنین نبایست زمان‌بندی ایجاد کنیم که در آن کاری بعد از مهلتش زمان‌بندی شود.چنین زمان‌بندی را غیرممکن (impossible) می‌نامیم.47

اسلاید 47: ج) زمان‌بندی با مهلت معینفرض کنید جدول زیر از کارها، مهلت و منفعتشان را داریم:وقتی گفته می‌شود که کار 1 دارای مهلت 2 است یعنی ...این کار می‌تواند در زمان 1 یا 2 شروع شود.در این جا زمان صفر وجود ندارد.در این جدول مثلا کار 2 به دلیل اینکه دارای مهلت 1 است فقط می‌تواند در زمان 1 شروع شود.48Job Deadline Profit 1230213532254140

اسلاید 48: ج) زمان‌بندی با مهلت معینزمان‌بندی‌های ممکن و کل منعت بدست آمده از آن در ادامه آمده است ...49Job Deadline Profit 1230213532254140

اسلاید 49: ج) زمان‌بندی با مهلت معینترتیبی از کارها ممکن (feasible sequence) گفته می‌شود اگر ..تمامی کارها در آن ترتیب بر اساس مهلتشان شروع شوند.مثلا ترتیب [4,1]، ترتیبی ممکن و ترتیب [1,4] ترتیبی ممکن نمی‌باشد.مجموعه‌ای از کارها مجموعه ممکن (feasible set) نامیده می‌شود اگر ...حداقل یک ترتیب ممکن از کارها بتوان از آن مجموعه استخراج کرد.مجموعه {2,4}، مجموعه‌ای ....ممکن نیست چرا که هیچ ترتیب ممکنی نمی‌توان از آن استخراج کرد.50Job Deadline Profit 1230213532254140

اسلاید 50: ج) زمان‌بندی با مهلت معینهدف ما در این مساله، یافتن ترتیبی ممکن است که ...بیشترین مجموع منفعت را دارا باشدوچنین ترتیبی ترتیب بهینه و ...مجموعه کارهای آن را ...مجموعه بهینه از کارها می‌نامیم.51

اسلاید 51: ج) زمان‌بندی با مهلت معینالگوریتم حریصانه سطح بالاکارها را بر اساس منفعتشان به صورت نزولی مرتب می‌کنیمS = Øwhile (the instance is not solved){ select next job; // selection procedure if (S is feasible with this job added) // feasibility check add this job to S; if (there are no more jobs) // solution check the instance is solved;}52

اسلاید 52: ج) زمان‌بندی با مهلت معین53کارها بر اساس منفعت مرتب‌شده هستند.S is set to Ø.S is set to {1} because the sequence [1] is feasible.S is set to {1,2} because the sequence [2,1] is feasible.{1,2, 3} is rejected because there is no feasible sequence for this set.S is set to {1,2,4} because the sequence [2,1,4] is feasible.{1,2,4,5}is rejected because there is no feasible sequence for this set.{1,2,4,6}is rejected because there is no feasible sequence for this set.{1,2,4,7}is rejected because there is no feasible sequence for this set.Job Deadline Profit 1340213531304325512063157210در این مثال S در نهایت با {1,2,4} برابر خواهد شد.

اسلاید 53: ج) زمان‌بندی با مهلت معینfunction J=schedule(deadline) n=length(deadline); J(1)=1; for i=2:n K=add(J,i,deadline); if feasible(K,deadline) J=K; end endend54function K=add(J,i,deadline) n=length(J); for r=1:n if deadline(J(r))<=deadline(i) K(r)=J(r); else K(r)=i; K(r+1:n+1)=J(r:n); break; end endendfunction r=feasible(K,deadline) n=length(K); r=1; for i=1:n if deadline(K(i))> i r=0; break; end endendبه گونه‌ای اضافه می‌کند که در دنباله به دست آمده کارها بر اساس مهلتشان مرتب باشند

اسلاید 54: ج) زمان‌بندی با مهلت معینپیچیدگی محاسباتی مرتب کردن کارها بر اساس منافعشان ... Θ (n lgn) می‌باشد. در هر تکرار از حلقه تابع schedule، ...برای اینکه iامین کار را به K اضافه کنیم، حداکثر به i مقایسه نیاز است. همچنین حداکثر i مقایسه نیاز است تا ممکن بودن K را بررسی کنیم.بنابراین در بدترین حالت پیچیدگی محاسباتی این الگوریتم برابر است با :55

اسلاید 55: که wi و pi و W همگی اعداد مثبتی هستند. می‌خواهیم زیر مجموعه A از S را به گونه‌ای مشخص کنیم که ...56مسئله کوله‌پشتی صفر و یک

اسلاید 56: ه) الگوریتم حریصانه در مسئله کوله پشتی صفر و یکاگر بخواهیم رویکرد brute-force را درنظر بگیریم ...باید تمامی زیرمجموعه‌های S را درنظر بگیریم و ...از اونهایی که مجموع وزنشون از W بیشتر است صرفنظر کنیم و ...از زیرمجموعه‌های باقیمانده اونی که بیشترین مجموع منفعت دارد را به عنوان پاسخ انتخاب کنیم.پیچیدگی محاسباتی این روش بادرنظر گرفتن n آیتم ....2n می‌باشد57

اسلاید 57: ه) الگوریتم حریصانه در مسئله کوله پشتی صفر و یکاولین راه حل حریصانه که شاید برای این مساله به ذهن برسد آن است که ...تمامی آیتم‌ها را بر اساس منفعتشان به صورت نزولی مرتب کنیم و ...به ترتیب آیتم‌ها را از مجموعه مرتب‌شده برداریم مادامیکه ...مجموع وزنشان از W بیشتر نشود.این استراتژی زمانیکه آیتم‌های با منفعت بالا وزن بیشتری در مقایسه با منفعتشون دارند مناسب نمی‌باشد.58

اسلاید 58: ه) الگوریتم حریصانه در مسئله کوله پشتی صفر و یکاحتمالا استراتژی بعدی این می‌تواند باشد که آیتم‌های سبک‌تر را ابتدا برداریم ...این استراتژی هم زمانی که آیتم‌های سبک منفعت کمی داشته باشند به شکست می‌انجامد.59

اسلاید 59: ه) الگوریتم حریصانه در مسئله کوله پشتی صفر و یکراه حل حریصانه مناسب این است که ...آیتم‌ها را بر اساس منفعت واحد وزنشان به صورت نزولی مرتب کنیم و ...آیتم‌ها را تا زمانیکه مجموع وزنشان از W بیشتر نشود برداریم.60

اسلاید 60: ه) الگوریتم حریصانه در مسئله کوله پشتی صفر و یک61

اسلاید 61: ه) الگوریتم حریصانه در مسئله کوله پشتی کسری (Fractional) در مساله کوله‌پشتی کسری چنانچه برداشتن کل آیتم میسر نیست، می‌توان بخشی از آن را نیز برداشت.مثلا در مثال قبل ...بنابراین هیچ فضایی هدر نمی‌رود. پس همواره حل بهینه را خواهیم داشت.62