include iostream include time include locale include conio using names

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
#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;
}