کوله پشتی صفر و یک

Question

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

#include<iostream>
#include"conio.h"
using namespace std;
void sort(float[]);
void knapsack(int,int,int);
bool promising(int);
int n;
int *p=new int[n];
int *w=new int[n];
float *array1=new float [n];
int profit=0;
int weight=0;
int W=13;
int maxprofit=0;
int *include=new int [n];
int totweight;
float bound;

int main()
{
 cout<<"enter n:";
 cin>>n;
 cout<<"enter p[i]";
 for(int i=0;i<n;i++)
     cin>>p[i];
 cout<<"enter w[i]";
 for(int i=0;i<n;i++)
     cin>>w[i];
 for(int i=0;i<n;i++)
     array1[i]=p[i]/w[i];
 sort(array1);
 cout<<"array"<<endl;
 for(int i=0;i<n;i++)
     cout<<"p[i]"<<p[i]<<endl;
 int i=0;
 knapsack(i,profit,weight);
  for(int i=0;i<n;i++)
 {
     cout<<"include["<<i<<"] "<<include[i]<<endl;
  }
 getch();
}
 void sort(float array1[])
  {
      for(int i=0;i<n-1;i++)
      {
          for(int j=i+1;j<n;j++)
          {
              if(array1[i]<array1[j])
      {
          int temp=p[i];
          p[i]=p[j];
          p[j]=temp;
          int temp1=w[i];
          w[i]=w[j];
          w[j]=temp;
      }
          }
      }
  }
 void knapsack(int i, int profit, int weight)
 {
     if(weight<=W && profit>maxprofit)
     {
         maxprofit=profit;
     }
     if(promising(i))
     {
         include[i+1]=1;
         knapsack(i+1, profit+p[i+1], weight+w[i+1]);
         include[i+1]=0;
         knapsack(i+1, profit, weight);
     }
 }
 bool promising(int i)
 {
     int j,k;
     if(weight>W)
         return false;
     else
     {
         j=i+1;
         bound=profit;
         totweight=weight;
         while(j<=n && totweight+w[i]<=W)
         {
             totweight=totweight+w[i];
             bound=bound+p[i];
             j++;
         }
         k=j;
         if(k<=n)
             bound=bound+(W-totweight)*p[k]/w[k];
         if(bound>maxprofit)
             return true;
         else
             return false;
     }
 }

 

Comments

سلام کدت رو بزار .

---

چاپ کردن مقادیر منفی یعنی اینکه شما به مکان هایی از حافظه که مقدار دهی نشدن دسترسی پیدا کردی. یا به اون آرایه مقدار ندادی.

---

سلام.دوستان.
هیچکی نمیدونه مشکل چیه؟

---

حل شد مشکلت ؟

---

سلام دوست عزیز.

خیلی ممنون از راهنمایی که کردید.

صورت کلی سوال به این صورته:

سوال:کوله ای داریم که حداکثر وزن Wرا تحمل می کند و n شی  داریم که که هر کدام قیمت یا ارزش pi و وزن wi دارد.
کوله پشتی چگونه پر کنیم که بیشترین سود را داشته باشد?

در کد من آرایه اگر شامل یک آیتم بود 1 واگر شامل آیتم نبود صفر در آن قرار می گیرد.

با توحه به راهنمایی هایی که کردید کد رو  تغییر دادم ولی فکر میکنم اونجایی که آرایه ها روglobal  تعریف کردم اشتباس.

وکد اجرا نمیشه.

لطفا بازم راهنماییم کنید.

اینم کد:
#include<iostream>
#include"conio.h"
using namespace std;
void sort(float[]);
void knapsack(int,int,int);
bool promising(int);
int n;
int *p;
int *w;
float *array1;
int profit=0;
int weight=0;
int W=13;
int maxprofit=0;
int *include;
int totweight;
float bound;
int main()
{
 cout<<"enter n:";
 cin>>n;
int *p=new int[n];
int *w=new int[n];
 float *array1=new float [n];
cout<<"enter p[i]";
 for(int i=0;i<n;i++)
     cin>>p[i];
 cout<<"enter w[i]";
 for(int i=0;i<n;i++)
     cin>>w[i];
 for(int i=0;i<n;i++)
     array1[i]=p[i]/w[i];
 sort(array1);
 cout<<"array"<<endl;
 for(int i=0;i<n;i++)
     cout<<"p[i]"<<p[i]<<endl;
 int i=0;
 knapsack(i,profit,weight);
  for(int i=0;i<n;i++)
 {
     cout<<"include["<<i<<"] "<<include[i]<<endl;
  }
 getch();
}
void sort(float array1[])
  {
       for(int i=0;i<n;i++)
         {
             for(int j=0;j<n-1;j++)
               {
        if(array1[j]<array1[j+1])
        {
            int temp=p[j];
            p[j]=p[j+1];
            p[j+1]=temp;
            int temp1=w[j];
            w[j]=w[j+1];
            w[j+1]=temp;
       }
    }
}
}

 void knapsack(int i, int profit, int weight)
 {
     if(weight<=W && profit>maxprofit)
     {
         maxprofit=profit;
     }
     if(promising(i))
     {
         include[i+1]=1;
         knapsack(i+1, profit+p[i+1], weight+w[i+1]);
         include[i+1]=0;
         knapsack(i+1, profit, weight);
     }
 }
 bool promising(int i)
 {
     int j,k;
     if(weight>W)
         return false;
     else
     {
         j=i+1;
         bound=profit;
         totweight=weight;
         while(j<=n && totweight+w[i]<=W)
         {
             totweight=totweight+w[i];
             bound=bound+p[i];
             j++;
         }
         k=j;
         if(k<=n)
             bound=bound+(W-totweight)*p[k]/w[k];
         if(bound>maxprofit)
             return true;
         else
             return false;
     }
 }

Answer 1

اولین مشکلی که توی کدتون دیده میشه گرفتن اشتباه حافظه تو خط 7-8-9 -15-10 ست

int *p=new int[n];
int *w=new int[n];
float *array1=new float [n];
int *include=new int [n];

اینارو باید بعد از گرفتن n از ورودی و داخل main بزاری فقط تعریفشون بزار global باشه . (یعنی تو کد شما الان اول حافظه گرفته میشه با یک n الکی بعد main اجرا میشه و n خونده میشه پس چاپ شدن مقدار منفی طبیعیه !)

مشکل دوم توی این خطه :

array1[i]=p[i]/w[i];

این جا ممکنه تقسیم به 0 انجام بشه پس بهتر قبل از تقسیم w چک بشه که 0 نباشه

مشکل بعدی توی sort َشماست Bubble sort به این شکله : (البته بهتره از یک الگوریتم دیگه استفاده کنی به جای Bubble sort ! )

      for(int i=0;i<n;i++)
      {
          for(int j=0;j<n-1;j++)
          {
              if(array1[j]<array1[j+1])
              {
                  int temp=p[j];
                  p[j]=p[j+1];
                  p[j+1]=temp;
                  int temp1=w[j];
                  w[j]=w[j+1];
                  w[j+1]=temp;
             }
          }
      }

 

بعد این که از اون جایی که من دقیق نمی دونم knapsack جیه درباره درستی الگوریتمت دیگه نمی تونم نظر بدم بهتر بود یک توضیح مختصر هم درباره کوله پشتی 0و1 میدادی .