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

مسئله کوله پشتی چیست؟
فرض کنید که جهانگردی می خواهدکوله پشتی خود را با انتخاب حالتهای ممکن از بین وسائل گوناگونی که بیشترین راحتی را برایش فراهم می سازند پر کند. این مسئله می تواند با شماره گذاری این وسائل از ۱ تا n و تعریف برداری از متغیرهای دودویی(Binary) (j = 1,2,…n) بصورت ریاضی فرمول بندی شود. به این معنی که: اگر شیء j ام انتخاب شود در غیر اینصورت وقتی میزان راحتی باشد که وسیله j ا م فراهم می آورد و وزن آن و c اندازه کوله پشتی باشد. مسئله ما انتخاب برداری از بین بردارهای دودویی x است،که محدودیت را بر آورده کند. بطوریکه تابع هدف ماکزیمم مقدار خود را بگیرد به عنوان نمونه ای از مسائلی که می توانند بصورت مساله کوله پشتی فرمول بندی شوند، مسئله زیر را در نظر بگیرید: فرض کنید که شما مایل به سرمایه گذاری همه یا قسمتی ازسرمایه تان باشید. اگر مبلغی که برای سرمایه گذاری در نظر گرفتید c دلار باشد و n مورد برای سرمایه گذاری ممکن باشد ، اجازه دهیدکه سود حاصل از سرمایه گذاری j ام و مقدار دلارهایی باشد که آن سرمایه گذاری لازم دارد . بدین ترتیب جواب بهینه مسئله کوله پشتی که تعریف کردیم به ما این امکان را می دهدکه بهترین حالت ممکن را از بین حالتهای مختلف سرمایه گذاری انتخاب کنیم. در این رابطه باید روشی برای حل این مسئله پیدا کرد . یک روش ابتدایی که در نگاه اول توجه ما را به خود جلب می کند ، عبارت از برنامه نویسی برای کامپیوتر به منظور امتحان کردن تمامی بردارهای دودویی ممکن x است، تا از بین بردارهایی که محدودیت مسئله را ارضاء می کنند بهترین را انتخاب کند. متاسفانه تعداد چنین بردارهایی است.بطوریکه یک کامپیوتر فرضی که می تواند یک بیلیون بردار را در یک ثانیه امتحان کند؛برای n = 60 بیش از ۳۰ سال وقت لازم دارد و بیش از ۶۰ سال برای n = 61 و دهها قرن برای n = 65 والی اخر. با این وجود ،با استفاده از الگوریتمهایی خاص می توان در بسیاری موارد مسئله ای با n = 100 000 را در عرض چند ثانیه روی یک کامپیوترکوچک حل کرد.

این برنامه با فرض این است که اشیا براساس وزن به صورت مرتب و صعودی به ورودی داده شوند. و در نهایت مشخص می کند کدام شی را بر داریم.

پسورد:  dataprocess.blogfa

سورس برنامه هشت وزیر به زبان ++C

هشت وزیر را در هشت خانه شطرنج (  ۸ * ۸ )  طوری قرار دهید که هیچکدام یکدیگر را تهدید نکنند. وزیر در خانه های شطرنج به صورت عرضی،طولی و قطری می تواند حرکت کند. این مسئله قابل تعمیم به مسئله N وزیر در یک شطرنج N*N است.

تاریخچه: این مسئله در سالی ۱۸۴۸ توسط شطرنج بازی به نام Max Bezzel عنوان شد و ریاضی دانان بسیاری ازجمله Gauss و Georg Cantor بر روی این مسئله کار کرده و در نهایت آنرا به N وزیر تعمیم دادند. اولین راه حل توسط Franz Nauck در سال ۱۸۵۰ ارائه شد که به همان مسئله N وزیر تعمیم داده شد. پس از آن Gunther راه حلی با استفاده از دترمینان ارائه داد که J.W.L. Glaisher آنرا کامل نمود.
در سال ۱۹۷۹ ، Edsger Dijkstra با استفاده از الگوریتم عقب گرد اول عمق این مسئله را حل کرد.

#include
#include
#include
#include 

const int m=20;
int k[m][m];
int Count=0;
int v=0 , n=0 , i=0 , j=0 , state=0;

void remove(int i,int j)
{
      int p,q;
      k[i][j]=0;
      Count--;
      for(p=0;p=0 && q>=0)
      {
               k[p--][q--]--;
      }
     p=i+1;
      q=j-1;
     while(p=0)
      {
               k[p++][q--]--;
      }
     p=i-1;
      q=j+1;
     while(p>=0 && q=0 && q>=0)
      {
               k[p--][q--]++;
     }
      p=i+1;
     q=j-1;
     while(p=0)
     {
                    k[p++][q--]++;
     }
     p=i-1;
     q=j+1;
      while(p>=0 && q<<<'.';
                     else
                                   cout<<<'X';
                 }
             cout<<<<<<"Total states founded for "<<<"*"<<<" boards and "<<<" Queens: "

<<<<<<"Press q to exit or any key to continue...";
                 int c=getch();
                      if(c=='q')exit(0);
     }
}

void move(int p,int q)
{
     apply(p,q);
     check();
      for(int i=p;i<<"**************Queens******************"<<<<"Enter size of board :";     cin>>n;
    cout<<"Enter number of queens:";     cin>>v;
     clrscr;
    draw();
     for(i=0;i<<"Total states:"<<