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

یکشنبه ۴ اسفند ۱۳۹۸
بازدید ۲,۱۷۱ نفر
AmRo
(20 امتیاز از 4 رای)
Loading...

تصویر knapsack-problem-in-cpp_8193 سورس مسئله کوله پشتی به زبان C++

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

در این بخش سورس مسئله کوله پشتی به زبان C++ را برای شما آماده کرده ایم که در محیط نرم افزار Code::Blocks و زبان برنامه نویسی سی پلاس پلاس نوشته شده است. در ادامه می توانید توضیحات، تصاویر و همچنین فیلمی از نحوه اجرا شدن پروژه را مشاهده کنید.

توضیحات پروژه

در این پروژه بعد از اجرا شدن برنامه، ابتدا ظرفیت کوله پشتی، تعداد اقلام موجود و سپس ارزش و وزن هر یک از اقلام از ورودی گرفته می شود. بعد از آن برنامه با استفاده از روش حریصانه اولویت برداشتن اقلام و مجموع ارزش قابل جا دادن در کوله پشتی را محاسبه کرده و در خروجی چاپ می کند.

مسئله کوله پشتی (Knapsack یا Rucksack)، مسئله ای برای بهینه سازی ترکیبیاتی است. فرض کنید مجموعه ای از اشیا، که هر کدام داری وزن و ارزش خاصی هستند در اختیار دارید. به هر شی تعدادی را تخصیص دهید به طوری که وزن اشیا انتخاب شده کوچکتر یا مساوی حدی از پیش تعیین شده، و ارزش آنها بیشینه شود. علت نامگذاری این مسئله، جهانگردی است که کوله پشتی ای با اندازه ی محدود دارد و باید آن را با مفیدترین صورت ممکن از اشیا پر کند.

معمولا در تخصیص منابع با محدودیت های مالی، با این مسئله روبرو هستیم. همچنین مسائلی از این قبیل در ترکیبیات، نظریه پیچیدگی محاسباتی، رمزنگاری و ریاضیات کاربردی به چشم می خورد.

قسمت های از سورس کد

#include <conio.h>
#include <iostream>
using namespace std;
void sortbyvw(int values[],int weights[],int n)
{
 int i,temp,j;
 for (i=0;i<=n-1;i++)
  	for (j=i+1;j<=n;j++)
     if(((float)values[i]/weights[i])<((float)values[j]/weights[j]))
     {
     		temp=values[i];
     		values[i]=values[j];
     		values[j]=temp;

     		temp=weights[i];
     		weights[i]=weights[j];
     		weights[j]=temp;
    }
}
int main()
{
    int y = 4;
 int values[100], weights[100];
     int n,maxWeight;
     cout<<"nEnter Capacity of Knapsack: ";
     cin>>maxWeight;

     cout<<"Enter Number of Things: ";
     cin>>n;
     for (int i=0;i<n;i++)
     {
      cout<<"nEnter the Value["<<i+1<<"]: ";
      cin>>values[i];
      cout<<"nEnter the Weight["<<i+1<<"]: ";
      cin>>weights[i];
      cout<<" V/W is: "<<(float)values[i]/weights[i] << endl;
      cout<<".......................................n";
     }
 cout<<"nn Maximum Value of Knapsack: " <<knapsack(values,weights,n-1,maxWeight) << endl;
 getch();
}