#include < iostream>
#include <time.h>
#include <locale>
#include <conio.h>
using namespace std;
double Count(double* a, int* b, int n){
double s=0;
for (int i = 0; i < n; i++)
s+=a[i]*b[i];
return s;
}
int main(){
setlocale (LC_ALL, "Rus");
double W;
int n,j,l;
cout << "Введите количество предметов:\n";
cin >> n;
cout << "Введите максимальную грузоподъемность рюкзака:\n";
cin >> W;
double maxPrice = 0, weight = 0;
double* c=new double [n];
double* w=new double [n];
int *k=new int [n];
int *b=new int [n];
int *max=new int [n];
for (int i=0;i<n;i++) max[i]=0;
for (int i=0;i<n;i++) b[i]=0;
srand(time(NULL));
for (int i=0;i<n;i++){
c[i]=rand()%10+1;
w[i]=rand()%10+1;
k[i]=rand()%50+1;
}
cout << endl;
cout << "№\tЦена\tМасса\tКоличество\n";
for (int i = 0; i < n;i++)
cout << i + 1 << "\t" << c[i] << "\t" << w[i] << "\t" << k[i] << endl;
cout << endl;
for (int i = 0; i < n;i++)
if (W/w[i]<k[i])
k[i]=W/w[i];
cout<<endl;
cout<<"Возможные комбинации: "<<endl;
while (true){
for (int i=0;i<n;i++){
cout << b[i] << " ";
}
cout << " W: "<< Count(w,b,n) << " С: " << Count (c, b ,n) << " Вес рюкзака: " << W << endl;
cout << endl;
getch();
cout << endl;
if (Count(w,b,n)<=W) {
if (Count(c,b,n)>=maxPrice && Count(w,b,n)<=W)
{
for (int i=0;i<n;i++)
max[i]=b[i];
maxPrice=Count(c,b,n);
}
for (j=n-1;j>=0 && b[j]==k[j];j--) b[j]=0;
if (j==-1) break;
if (j!=-1) b[j]++;
}
if (Count(w,b,n)>W)
{
for (l = n-1 ;l >= 0; l--)
if (b[l]) break;
b[l]=0;
l--;
for (j=l;j>=0 && b[j]==k[j];j--) b[j]=0;
if (j==-1) break;
if (j!=-1) b[j]++;
}
}
cout << endl;
cout << "Лучшая комбинация: ";
for (int i=0;i<n;i++) cout << max[i] << " ";
cout << endl;
cout << "Общий вес: "<< Count(w,max,n) << endl;
cout << "Лучшая стоимость: " << maxPrice << endl;
delete [] c;
delete [] w;
delete [] k;
delete [] b;
delete [] max;
return 0;
}