الگوریتم گریدی برای مساله کوله پشتی با مطلب
سريعترين راه براي يافتن يك جواب تقريبي 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