Рюкзак cpp определяет точку входа для консольного приложения include s

  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
105
106
// Рюкзак.cpp: определяет точку входа для консольного приложения.
//
#include "stdafx.h"
#include <iostream>
#include <time.h>
#include <locale>
using namespace std;
double sum(double* a, int* b, int n){
double summa=0;
for (int i=0;i<n;i++) summa+=a[i]*b[i];
return summa;
}
int main()
{ setlocale (LC_ALL, "Rus");
double W_max;
int n,j,l;
cout<<"Сколько предметов\n";
cin>>n;
cout<<"Максимальный груз рюкзака\n";
cin>>W_max;
double C_max=0,weight=0;
double* c=new double [n];
double* w=new double [n];
int *k=new int [n];
int *b=new int [n];
int *b_max=new int [n];
for (int i=0;i<n;i++) b_max[i]=0;
for (int i=0;i<n;i++) b[i]=0;
for (int i=0;i<n;i++) c[i]=rand()%10+10;
cout<<"Стоимости предметов\n";
for (int i=0;i<n;i++) cout<<c[i]<<" ";
cout<<endl;
for (int i=0;i<n;i++) w[i]=rand()%9+10;
cout<<"Массы предметов\n";
for (int i=0;i<n;i++) cout<<w[i]<<" ";
cout<<endl;
for (int i=0;i<n;i++) k[i]=rand()%9+100;
cout<<"Количество на складе\n";
for (int i=0;i<n;i++) cout<<k[i]<<" ";
for (int i=0;i<n;i++) if (W_max/w[i]<k[i]) k[i]=W_max/w[i];
cout<<endl;
for (int i=0;i<n;i++) cout<<k[i]<<" ";
cout<<endl;
cout<<"Возможные комбинации "<<endl;
while (1){
for (int i=0;i<n;i++) cout<<b[i]<<" ";
cout<<endl;
if (sum(w,b,n)<=W_max) {
if (sum(c,b,n)>=C_max && sum(w,b,n)<=W_max)
{for (int i=0;i<n;i++) b_max[i]=b[i];
C_max=sum(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 (sum(w,b,n)>W_max)
{ 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;
for (int i=0;i<n;i++) cout<<b_max[i]<<" ";
cout<<endl;
cout<<"Вес "<< sum(w,b_max,n)<<endl;
cout<<"Стоимость "<<C_max<<endl;
delete [] c;
delete [] w;
delete [] k;
delete [] b;
delete [] b_max;
return 0;
}