نمايش پست تنها
قديمي ۰۸-۱-۱۳۸۸, ۰۹:۲۴ بعد از ظهر   #10 (لینک دائم)
Astaraki Female
Administrator
 
آواتار Astaraki
 
تاريخ عضويت: خرداد ۱۳۸۷
محل سكونت: تهران-کرج!
پست ها: 3,465
تشكرها: 754
16,300 تشكر در 3,124 پست
My Mood: Mehrabon
ارسال پيغام Yahoo به Astaraki
Cool

الگوریتم گریدی برای مساله کوله پشتی با مطلب

سريعترين راه براي يافتن يك جواب تقريبي KP استفاده از اين واقعيت است كه جواب آزاد سازي پيوسته مسئله فقط داراي يك متغير اعشاري است. الگوریتم گریدی از این مطلب برای حل مساله کوله پشتی استفاده می نماید. می توان ثابت کرد که جواب بدست آمده بطور متوسط نزدیک به جواب بهینه است.
برنامه الگوريتم گريدي برای مساله کوله پشتی با مقادیر ۰ و ۱ به زبان مطلب و بصورت پنجره فعال بصورت زیر است.
فرض می شود اشیا براساس نسبت وزنی مرتب شده اند
كد:
n=input('n = ');
c=input('c = ');
d=1:n;
p=input('(pj) = ');
w=input('(wj) = ');
 
bn=0;
for bb=1:n-1;
    if (p(bb)/w(bb))<(p(bb+1)/w(bb+1))
        bn=1;
        break;
    end
end
if bn>0
    ERROR=' The items not sorted correct  TRY AGAIN '
    break;
end
 
cc=c;
s=0;
jj=1;
for j=1:n
    if w(j)>cc
        d(j)=0;
    else
        d(j)=1;
        cc=cc-w(j);
        s=s+p(j);
    end
    if p(j)>p(jj)
        jj=j;
    end
end
if p(j)>s
    s=p(jj);
    for j=1:n
        d(j)=0;
    end
    d(jj)=1;
end
x=d
zq=s
Astaraki آفلاين است   پاسخ با نقل قول
از Astaraki تشكر كرده اند:
green_Dream (۰۱-۲۳-۱۳۸۹), روحي (۰۵-۲۶-۱۳۹۲)