PDA

View Full Version : الگوریتم های کوله پشتی



aloneman2005
جمعه 04 تیر 1389, 19:56 عصر
سلام من می خوام برنامه الگوریتم کوله پشتی رو بنویسم ولی هیچی ازش نمی دونم ممنون می شم برام توضیح بدین.
انواع کوله پشتی 1 صفر و یک 2 - کسری
کدام یک بهتر است الگوریتم های آن ها فرق می کند یا نه ؟
انواع الگوریتم های آن .
الگوریتم حریصانه .... پویا ....تقسیم و غلبه ... مکاشفه ای

aloneman2005
شنبه 05 تیر 1389, 00:15 صبح
من یه الگوریتم حریصانه برای صفر و یک نوشتم لطفا نظر بدید .

int Grady_knapsack(int p[],int w[],int n,int W);

int main()
{
int p[]={50,60,140};
int w[]={5,10,20};
Grady_knapsack(p,w,3,30);


}
int Grady_knapsack(int p[],int w[],int n,int W)
{
int c[100]={0};
for (int i=0;i<n;i++)
c[i]=p[i]/w[i];
///////////////
for (int i=0;i<n;i++)
for (int j=0;j<n-1;j++)
if (c[j]<c[j+1])
{
float temp=c[j];
c[j]=c[j+1];
c[j+1]=temp;
//////////////
int t=p[j];
p[j]=p[j+1];
p[j+1]=t;
/////////////
t=w[j];
w[j]=w[j+1];
w[j+1]=t;
}
int s=0;
int profit=0;
for (int i=0;i<n;i++)
{
if ((s+w[i])<=W)
{
s=s+w[i];
profit +=p[i];

}
else
break;
}
////////////////////////////////
return profit;

}