#include <cstdlib>
#include <iostream>
/*Известен вес P[1], P[2], P[n] каждого из n предметов.
Как разместить их в наименьшем числе рюкзаков,
если грузоподъёмность каждого рюкзака равна q*/

using namespace std;

//создание текстового файла store.txt из n натуральных чисел
void create()
{   int max; //максимальное знаение веса предмета 
    int n;   //количество предметов
    int i;
    printf("nput maximum weight of objekt:  max=");
    scanf("%d",&max);
    printf("input quantity of objekts:  n = ");
    scanf("%d",&n);
    int *p;  //массив из n случайных чисел
    p=new int[n+1];
    srand(time(NULL));
    p[0]=0;
    for (i=1; i<=n; i++) p[i]=rand()%max+1;
    FILE *g;
    g=fopen("store.txt","w");
    for (i=1; i<=n; i++) fprintf(g,"%d\n",p[i]);
    fclose(g);
}

//проверка существовавния текстового файла dat.txt  
int experiment() 
{
    FILE *g;
    g=fopen("store.txt", "r");
    if (g == NULL)  return 1;
    fclose(g);
}

void rucksack()
{
    int q;  // грузоподъёмность каждого рюкзака 
    int n;  //количество предметов
    int m;  //суммарный вес предметов в рюкзаке
    int k;  //количество предметов в рюкзаке
    int s;  //сумма
    int v;  //количество рюкзаков
    int w;  //суммарный вес всех предметов
    int i, j, r; 
    bool t;   //имеются нулевые элементы в сумме
    int min;  //минимальная грузоподъёмность рюкзака 
    v=0;
    w=0;
    FILE *g;
    g=fopen("store.txt","r");
    n=0;
    int o;   
    while(!feof(g)) {n++;fscanf(g,"%d\n",&o);}
    fclose(g);
    int *p;  //массив из n случайных чисел
    p=new int[n+1];
    g=fopen("store.txt","r");
    for (i=1; i<=n; i++) fscanf(g,"%d\n",&p[i]);
    fclose(g);
    min=p[1];
    for (i=2; i<=n; i++) if (p[i]>min) min=p[i];
    for (i=1; i<=n; i++) w=w+p[i];
    printf("Total weight of all objekts  = %d\n", w);
    do
    {  
      printf("input carrying capacity of rucksack g>=%d:  q = ", min);
      scanf("%d",&q);
    }
    while (q<min);  
    FILE *f;
    f=fopen("comb.txt","w");
    for (i=1; i<=n; i++) printf("P[%2d]=%2d\n",i,p[i]);
    printf("Total number of jbjekts  N=  %d  \n",n);
    fprintf(f,"Общее количество предметов N=  %d  \n",n);
    fprintf(f,"Вес каждого предмета:\n",n); 
    for (i=1; i<=n; i++) fprintf(f,"P[%2d] = %2d\n",i,p[i]);
    fprintf(f,"Грузоподъёмность рюкзака = %2d\n",q);
    fprintf(f,"Суммарный вес всех предметов = %d \n",w);
    m=q;
    while (m>0)
    {     
      int *a;    //массив из индексов 1..k
      for (k=1; k<=n; k++)
      { 
        a=new int[k+1];
        for (i=0; i<=k; i++)    a[i]=i;   
        j=0;  r=0; 
        while (j<=k-1)
        {
          s=0;  
          t=true;  
          for (i=1; i<=k; i++) {if (p[a[i]]==0) t=false; s=s+p[a[i]];}
          if ((s==m)&&(t==true)) 
          {
             v++; 
             fprintf(f,"В %d -й рюкзак вошли следующие предметы ",v); 
             printf("Rucksackk  %d\n", v); 
             for (i=1; i<k; i++) printf("P[%2d] + ", a[i]);
             printf("P[%2d] = %d\n", a[k],m); 
             for (i=1; i<k; i++) fprintf(f,"P[%2d] + ",a[i]);
             fprintf(f,"P[%2d] = %d\n",a[k],m); 
             for (i=1; i<=k; i++) p[a[i]]=0;   
          }
          while (a[k-j]==n-j) j++;
          a[k-j]++;
          for (r=0; r<j; r++) a[k-j+r+1]=a[k-j+r]+1; 
          if (j<=k-1) j=0; 
        }
      }
    m--;
    w=0;
    for (i=1; i<=n; i++) w=w+p[i];
    if (w<m) m=w; 
    }  
    fclose(f);
}

int main(int argc, char *argv[])
{   
    int v;
    v=experiment();
    if (v==1) 
      {
            printf("No textfile store.txt. Create it\n ");
            create();
       }
    rucksack();
    printf("look the file 'comb.txt' \n"); 
    system("PAUSE");
    return EXIT_SUCCESS;
}