الگوریتمی می خواهم که مسئله کوله پشتی را به روش حریصانه حل کند

[student of software]

با سلام ؛
الگوریتم حریصانه کوله پشتی ( پیاده سازی آن به زبان C )

توضیحات :
الگوریتم حریصانه با انجام یک سری انتخاب ، که هر یک در لحظه ای خاص بهترین به نظر می رسد عمل می کند ، یعنی انتخاب در جای خود بهینه است . به این شکل که به ترتیب عناصر داده ها را گرفته ، هر بار آن عنصری را که طبق ملاکی معین "بهترین" به نظر می رسد ، بدون توجه به انتخاب هایی که قبلا انجام داده یا در آینده انجام خواهد داد ، برمی دارد .
در مورد مسئله کوله پشتی مثالی از آن این است که فردی می خواهد وسایلش را داخل کوله پشتی اش بگذارد به شرطی که وزن کل قطعات از یک حد خاص W بالاتر نرود ، چون کوله پشتی پاره می شود . چون هر وسیله دارای ارزش و وزن معینی است ، تعیین حداکثر ارزش وسایل در حالی که وزن آن ها از W فراتر نرود اهمیت دارد. یعنی اگر ارزش وسایل را با P و وزن آن ها را با W مشخص کنیم روال انتخاب ما بصورت Pi/Wi می شود .

[Identifier]

با سلام ؛
الگوریتم حریصانه کوله پشتی ( پیاده سازی آن به زبان C ) اگر میخواهی کسی برات برنامه بنویسه، فکری بیهوده بیش نیست؛ اما اگر توی نوشتنش مشکل داری باید توی بخش C مطرح کنی و اگر میخواهی فقط از الگوریتمش اطلاع پیدا کنی هیمنجا سوال رو پیگیری کن.

توضیح خلاصه ای در باب الگوریتم فوق الذکر :

روش حریص در الگوریتمها اصولایکی از تکنیکهای مهم در طراحی الگوریتمها بشمار می اید و در حل طیف گسترده ای از مسائل از ان استفاده می شود، بیشتر این مسائل (نه همه شان) n تا ورودی دارند و ما نیاز داریم به مجموعه جوابی برسی مکه شرایط مرزی و محدود کننده را در صورت مسأله ارضا کند . هر مجموعه ای که این محدودیتها و شرایط مرزی را برآورده سازد در واقع یک راه حل(( ممکن ))خوانده می شود . ما به یافتن مجموعه ای نیاز داریم که راه حل(( ممکن)) را برای تابع مورد نظر بیابد.
راه حل(( ممکنی))که این نقش را برای ما بتواند ایفا کند، یک راه حل ‹‹ بهینه›› نامیده می شود .
روش حریص میگوید که شما می توانید الگوریتمی را ارائه دهید که بصورت گام به گام میباشد که در هر زمان یک ورودی دارند در هر گام این امر که ایا یک ورودی مخصوص، راه حل بهینه است یا نه ، تصمیم گیری و مشخص می شود . این کار با این فرض صورت می گیرد که ورودیها با ترتیبی مشخص و معین که به وسیله یک روال انتخاب گرفته می شوند، وارد گامهای الگوریتم می شوند ، حال اگر در یک گام یک ورودی آمد و در گام بعدی مشخص شد که ان ورودی به مجموعه جواب‹‹ ممکن››
نمی انجامد ، از مجموعه کل خروجی‌ (راه حل ممکن) کنار گذاشته می شود. این روال انتخابگر خود مبتنی بر برخی سنجشهای بهینه سازی است . این سنجش ممکن است همان تابع هدف باشد یا نباشد.
در واقع، چندین سنجش و اندازه گیری و یا همان راه کار برای تابع مورد نظر ما ، معقول هستند و اصولا غیر از این نمی تواند باشد،پس بسیاری از اینها ‹ راه حلهای بهینه› در الگوریتمهایی که برای راه حلهای فرعی بهینه هستند، به کار می ایند.
ما می توانیم روش حریص را بصورت مجرد و انتزاعی ولی بسیار دقیقتر از بالا توضیح دهیم . انتزاع کنترلی زیر را ببین:



Procedure GREEDY(A.n)
// A(1:n)contains the n inputs
solution <- 0 //initialize the solution to empty
for I  1 to n do
x <- SELECT (A)
if FEASIBLE (sulotion.x)
then sulotion <- UNION (sulotion.x)
end if
repeat
return (sulotion)
end GREEDY


در ساختار انتزاعی فوق برای روش حریص ‹ الگوریتم حریص› تابع SELECT ورودیها را از A انتخاب می کند . سپس آن را از مجموعه ورودیهای ممکن حذف کرده، مقدارش را بهx منتسب می کند .
FEASIBLE تابعی بولی است که مشخص می کند آیا x در بردار "حل" باشد یا نه ! ، UNION واقعا" x را به توابع هدف به هنگام درآمده اضافه می کند ( به مجموعه جواب مسأله )
روال GREEDY ، روش اساسی حل مسأله بصورت "حریص" را نشان می دهد ، وقتی یک مسأله با روش حریص حل می شود عنان کار به دست تابع GREEDY سپرده می شود و توابع FEASIBLE ، SELECT ، UNION به صورتی که در فوق آمده اند پیاده سازی می شوند تا حل مسأله به نتایج دلخواه برسد .
دقت کنید با روش حریص اینگونه با مساله کوله پشتی برخورد می شود :

شیء I دارای وزن w است . و کوله پشتی دارای ظرفیت M است . اگر جزء xi از شی I در کوله پشتی قرار گیرد آنگاه PiXi سودی است که ما به آن می رسیم حال هدف مسأله این است که با چه ترکیبی از اشیاء و اجزای آنها کوله پشتی را پر کنیم که حداکثر سود را ببریم در واقع می خواهیم : سیگما PiXi ماکزیمم شود . ضمنا" به این باید توجه داشته باشیم که سیگما WiXi کوچکتر مساوی Mباشد .
مثال زیر را در نظر بگیرید:


n=3,M=20 ,(P1,P2,P3)=(25,24,15),(W1,W2,W3)=(18,15,10)
داریم : Mچهار حالت برای پر کردن ظرفیت


1/2,1/3,1/4 16.5 24.25
1,2/15,0 20 28.2
0,2/3,1 20 31
0,1,1/2 20 31.5
که به ترتیب مقائیر ستون اول سیگما XiPi و ستون دوم سیگما XiWi و ستون سوم X1,X2,X3 است

همانطور که می بینیم در حالت چهارم بیشترین سود را می بریم . این یعنی روش حریص !



procedure GREEDY – KNAPSACK ( P , W , M , X , n )
real P (1:n),W(1:n),X(1:n),M,cu;
integer i,n;
X<-0
Cu<-M
For i<-1 to n do
If W(i)>cu then exit endif
X(i)<-1
Cu<-cu-W(i)
Repeat
If i<=n then X(i)cu/W(i) endif
end GREEDY - KNAPSACK


وقتی از روش حریص برای حل مسأله کوله پشتی استفاده می کنیم حداقل سه پارامتر مختلف را در مورد تعیین اینکه آیا گذاشتن شیء مشخصی در کوله پشتی به راه حل بهینه کمک می کند یا نه,مورد ارزیابی قرار می دهیم. این پارامتر ها عبارتند از :سود کلی ، ظرفیت مصرف شده ، و نسبت سود به ظرفیت مصرف شده .
وقتی یک پارامتر از پارامترهای بهینه سازی مزبور در نظر گرفته شده و حل مسأله به روش حریص ادامه می یابد ، سعی می شود که فقط آن پارامتر را به بهینه ترین حالت نزدیک کند !
مثلا" وقتی پارامتر سود به یک روش حریص سپرده می شود ، روش حریص شی ءای را پیشنهاد می کند که بیشترین سود را نصیب ما کند ! امّا وقتی پارامتر ظرفیت در نظر گرفته می شود الگوریتم حریص سعی می کند از حداقل ظرفیت استفاده کند . اگر تا اینجا قناعت کنیم روش حریص هرگز تضمین نمی کند که جواب بهینه را به خروجی بفرستد به همین علت نیز ما پارامتر سوم را باید حتما" مدنظر قرار دهیم :

اگر Pn / Wn ≤ … ≤ p2/w1 آنگاه الگوریتم فوق جواب بهینه را به دست می دهد .

[ساناز سعادتمند]

سلام من اگکوریتم کوله پشتی کسری به روش حریصانه را نیاز دارم
که ورودی ان: ارزش و وزن و عنصر باشد

[mortezamsp]

ن اگکوریتم کوله پشتی کسری به روش حریصان
ابتدا اقلام را مرتب میکنیم _ بصورت صعودی بر حسب نسبت قیمت به وزن _ سپس از شئ اول شروع میکنیم _شئی که نسبت ارزش به وزن آن از بقیه بیشتر است شروع میکنیم و در کوله پشتی قرار میدهیم_اگر از این قلم شئ چندتا بود تاوقتی کیسه پرنشود همه را میگذاریم _ ، سپس به سراغ قلم بعدی میروم و الی آخر ... در جاییکه کیسه ظرفیت پذیرفتن شئ را ندارد، بخشی از آن که در کیسه جا میشود را قرار میدهیم و اینجا کیسه پر میشود.