راهنمایی در مورد کوله پشتی0-1

[leilast]

سلام
میخواستم بدونم کسی میتونه در مورد الگوریتم و منطق برنامه کوله پشتی 0-1 یک سری توضیحات واضح و قابل فهم به من بده!
یه سری توضیحات و حتی الگوریتم و کد برنامه رو از کتاب آقای نقیب زاده خوندم ولی کامل متوجه نشدم.
یه جاهایی برام ابهام داره!!
میتونید کمکم کنید؟:اشتباه::اشتباه:

[whitehat]

در مسئله کوله پشتی صفر و یک x شی داریم که هر کدام دارای ارزش p هستند و وزن w را دارند.
می خواهیم اشیایی را در داخل کوله پشتی قرار دهیم که بیشترین ارزش را برداریم و وزن اشیا از ماکزیمم وزنی که کوله پشتی می خواهد تحمل کند ، بیشتر نشود.
هدف مسئله ماکزمم کردن مقدار
http://upload.wikimedia.org/math/3/3/a/33a10f5accb146d1c91a98b75790c217.png
و محدودیت آن درصورتیکه ماکزمم گنجایش کوله پشتی c باشد بصورت زیر است
http://upload.wikimedia.org/math/9/e/2/9e28d4f4305df35592e077c82ca0e692.png
این الگوریتم پیاده سازی های مختلفی دارد ، شما باید مشخص کنید کدام راه حل مد نظرتان است. قبلا در مورد روش حریصانه در این بخش هم بحث شده می توانید به آن بحث مراجعه کنید. اطلاعات تکمیلی را از اینجا (http://en.wikipedia.org/wiki/Knapsack_problem) بگیرید

[leilast]

راه حل مورد نظر من از برنامه سازی پویاست.
روش حریصانه این مسئله بیشتر مربوط به کوله پشتی غیر 0-1 میشه.
من خودم هم ایده ای برای این مسئله دارم:
به این ترتیب که در ابتدا ظرفیت ماکزیمم کوله پشتی را دریافت کنیم,
بعد از روی wها حالات مختلفی را که جمع wها برابر(M:ظرفیت کوله پشتی) میشود را پیدا کنیم ,یعنی ماکزیمم وزنی که کوله پشتی میتواند تحمل کند به ازای حالات مختلف جمع زدنها,
بعد با توجه به وزنهای استخراج شده ,ارزش(P) هر کدام از حالتها را بدست می آوریم و ماکزیم p ها ی بدست آمده حالات 0-1 را مشخص میکنیم.
مثلا m=7
p1,p2,p3,p4=3,1,4,5
w1,w2,w3,w4=2,4,3,1
w2+w3=7 p2+p3=5
w1+w4+w2=7 p1+p4+p2=7
ماکزیمم P ها در حالت دوم قرار دارد پس جواب مسئل{1,1,0,1 }= {x1,x2,x3,x3}
آیا این ایده درسته؟

[whitehat]

روش حریصانه این مسئله بیشتر مربوط به کوله پشتی غیر 0-1 میشه.
بهتره این جمله را این طور تصحیح کنید که روش حریصانه برای کوله پشتی غیر 0-1 جواب بهینه را می دهد.
نکته دیگر اینکه الگوریتم پویا برای کوله پشتی 0-1 بهترین جواب را می دهد(با کمترین هزینه)
ایده شما تا حدی درست است اگر در مورد "ارزش(P) هر کدام از حالتها را بدست می آوریم" توضیح بیشتری می دادید شاید بهتر می شد راهنمایی کرد.
در الگوریتم های پویا شما باید مسئله را از جز به کل حل کنید (این مرحله مانند روش تقسیم و حل است) و آنها را ذخیره کنید و در مراحل بعد با استفاده از نتایج بدست آمده بقیه الگوریتم را حل کنید.
توجه کنید هدف مسئله کوله پشتی بدست آوردن ماکزمم ارزش است نه کدام آیتم ها

البته می توان با توجه به پیاده سازی آیتم هایی که لازم است را بدست آورید .
این لینک (http://www.personal.kent.edu/%7Ermuhamma/Algorithms/MyAlgorithms/Dynamic/knapsackdyn.htm) این مسئله بطور کامل توضیح داده ، اگر سوالی بود بپرسید

[leilast]

این سورس کد کوله پشتی 0-1که با توجه به منطق همین لینکه
اما برنامه اشکال داره،جواب نمیده ،میشه در این مورد هم کمک کنید؟:اشتباه:

#include "iostream.h"
#include "conio.h"
void main() {
clrscr();
int i,j,n,l,p[10][20];
int weight,w[10],P[10];
cout<<"enter weight";
cin>>weight;
cout<<"enter your namber of objects";
cin>>n;
for(i=0;i<n;i++){
cout<<"enter w["<<i<<"]"<<"\n";
cin>>w[i];
cout<<"enter p["<<i<<"]"<<"\n";
cin>>P[i]; }
for(i=0;i<n;i++){
p[i][0]=0;
for(j=0;j<weight;j++){
p[0][j]=0;
for(i=1;i<n;i++){
for(j=1;j<weight;j++)
if(w[i]<=j){
if(p[i-1][j]<P[i]+p[i-1][j-w[i]]){
p[i][j]=(P[i]+p[i-1][j-w[i]]);
if(p[i-1][j]>P[i]+p[i-1][j-w[i]])
p[i][j]=p[i-1][j-w[i]];}
else
p[i][j]=p[i-1][j];
}
}

}
cout<< p[n][weight];}

getch();}

[ali643]

بهتره این جمله را این طور تصحیح کنید که روش حریصانه برای کوله پشتی غیر 0-1 جواب بهینه را می دهد.

همون کوله پشتی کسری دیگه.
آیا نوع های دیگه ای از الگوریتم کوله پشتی هست ؟؟؟

[whitehat]

اما برنامه اشکال داره،جواب نمیده ،میشه در این مورد هم کمک کنید؟چه پیغام خطایی می دهد؟

همون کوله پشتی کسری دیگه.بله

آیا نوع های دیگه ای از الگوریتم کوله پشتی هست ؟؟؟خیر (البته اگه bounded و unbounded را یکی بگیرید) -به لینکی که در پست 2 آمده مراجعه کنید

[leilast]

خطاها رو از بین بردم ولی خروجی فقط 0 چاپ میکنه!
یعنی اصلا حلقه ها اجرا نمیشه!!!!!!
نمیدونم کجاش اشکال داره؟
(در کد برنامه نسخه اصلاح شده رو گذاشتم)

[whitehat]

ورودی ها را چه اعدادی می دهید؟

[مرضی6711]

حل مسئله کوله پشتی با الگوریتم sa رو نیاز دارم. اگه میشه راهنمایی کنید