سلام دوست عزیز.
خیلی ممنون از راهنمایی که کردید.
صورت کلی سوال به این صورته:
سوال:کوله ای داریم که حداکثر وزن 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;
}
}