الگوریتم کوله پشتی در زبان C++

				
					
#include <conio.h>
#include <stdio.h>
#include <iostream.h>

void sortbypw(int p[],int w[],int n)
{
 int i,t,j;
 for (i=0;i<=n-1;i++)
  for (j=i+1;j<=n;j++)
     if(((float)p[i]/w[i])<((float)p[j]/w[j]))
         {
     t=p[i];
     p[i]=p[j];
     p[j]=t;
     t=w[i];
     w[i]=w[j];
     w[j]=t;
    }
}


////////////////////////////////////////////////////////////////////////


 class="lang:c++ decode:true"float knapsack(int p[],int w[],int n,int m)
{
sortbypw(p,w,n);
int w1=m;
int i=0;
float pp=0;
while (i<=n && w1>0)
 {
    if (w[i]<w1)
    {
     cout<<" p : "<<p[i];
     w1-=w[i];
     pp+=p[i];
     i++;
    }
    else
    {
     cout<<" p : "<<p[i];
     pp+=w1*((float)p[i]/w[i]);
    w1=0;
    }
 }
 return pp;
}

void main()
{
 int p[100]={6,12,7,18,9,30};
 int w[100]={1,5,3,9,5,20};
 clrscr();
 cout<<"If You Want Input Data Press (Y) Else Press (N) :";
 char ch=getche();
 if (ch=='n')
      cout<<"\n\n Arzesh Knapsack : "<<knapsack(p,w,5,20);
 else
     {
     int n,m;
     cout<<"\nEnter Weight Knapsack : ";
     cin>>m;
     cout<<"Enter Num : ";
     cin>>n;
     for (int i=0;i<n;i++)
     {
      cout<<"Enter Arzesh : ";
      cin>>p[i];
      cout<<"\nEnter Weight : ";
      cin>>w[i];
      gotoxy(20,wherey()-2);
      cout<<" P/W Is : "<<(float)p[i]/w[i];
      gotoxy(1,wherey()+2);
      cout<<".......................................\n";
     }
      cout<<"\n\n Arzesh Knapsack : "<<knapsack(p,w,n-1,m);
     }
 getch();
}

توضیحات:

صورت سوال:

الگوریتم کو‌له پشتی در زبان C++

فرض کنید که جهانگردی می‌خواهدکوله‌پشتی خود را با انتخاب حالت‌های ممکن از بین وسائل گوناگونی که بیشترین راحتی را برایش فراهم می‌سازند پر کند. این مسئله می‌تواند با شماره‌گذاری این وسائل از ۱ تا n و تعریف برداری از متغیرهای دودویی (Binary) (j = ۱٬۲٬۳…n) به صورت ریاضی فرمول بندی شود. به این معنی که: اگر شیء j ام انتخاب شود در غیر اینصورت وقتی میزان راحتی باشد که وسیله j ا م فراهم می‌آورد و وزن آن و c اندازه کوله‌پشتی باشد. مسئله ما انتخاب برداری از بین بردارهای دودویی x است که محدودیت را برآورده کند. بطوری‌که تابع هدف، بیشترین مقدار خود را بگیرد به عنوان نمونه‌ای از مسائلی که می‌توانند به صورت مسئله کوله‌پشتی فرمول بندی شوند، مسئله زیر را در نظر بگیرید: فرض کنید که شما مایل به سرمایه‌گذاری همه یا قسمتی ازسرمایه‌تان باشید. اگر مبلغی که برای سرمایه‌گذاری در نظر گرفتید c دلار باشد و n مورد برای سرمایه‌گذاری ممکن باشد، اجازه دهیدکه سود حاصل از سرمایه‌گذاری j ام و مقدار دلارهایی باشد که آن سرمایه‌گذاری لازم دارد.

نحوه حل مسئله:

بدین ترتیب جواب بهینه مسئله کوله‌پشتی که تعریف کردیم به ما این امکان را می‌دهدکه بهترین حالت ممکن را از بین حالت‌های گوناگون سرمایه‌گذاری انتخاب کنیم. در این رابطه باید روشی برای حل این مسئله پیدا کرد. یک روش ابتدایی که در نگاه نخست، توجه ما را به خود جلب می‌کند عبارت از برنامه‌نویسی برای رایانه به منظور امتحان کردن همه بردارهای دودویی ممکن x است، تا از بین بردارهایی که محدودیت مسئله را ارضاء می‌کنند بهترین را انتخاب کند. متأسفانه تعداد چنین بردارهایی است. بطوری‌که یک رایانه فرضی که می‌تواند یک بیلیون بردار را در یک ثانیه امتحان کند؛ برای n = ۶۰ بیش از ۳۰ سال وقت لازم دارد و بیش از ۶۰ سال برای n = ۶۱ و ده‌ها سده برای n = ۶۵ والی آخر. با این وجود با استفاده از الگوریتم‌هایی خاص می‌توان در بسیاری موارد مسئله‌ای با n = ۱۰۰ ۰۰۰ را در عرض چند ثانیه روی یک رایانه کوچک حل کرد.

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

شما میتوانید سوالات خود را از طریق ایمیل پشتیبانی – تماس با ما – یا در قسمت نظرات سوال خود را بپرسید.