Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > C/C++: Общие вопросы > Задача про грузы.

Автор: Kot 29.7.2006, 21:03

Программа либо ничего не выводит на экран, либо вылетает.
Условие задачи:
1. Вводится некоторая грузоподьемность грузовика;
2. Вводятся число грузов и масса каждого из них.
Найти номера грузов, которые необходимо оставить, чтобы грузовик был нагружен максимально.

Код


#include <conio.h>
#include <stdio.h>
#include <alloc.h>
#include <stdlib.h>
void main(){
 int i,j,k,s,z,temp,gruz,maxi,Ng;
 int* a;
 int** max;
 int** num;
 printf("Vvedite gruzopod'emnost': ");
 scanf("%d",&gruz);
 printf("Vvedite kolichestvo gruzov:\n");
 scanf("%d",&Ng);
 
 a=(int*) malloc (Ng*sizeof(int));
 
 max=(int **) malloc (Ng*sizeof(int*));
 for (i=0; i<Ng; i++)
 *(max+i)=(int *) malloc (4*sizeof(int));
 
 num=(int**) malloc (Ng*sizeof(int *));
 for (i=0; i<Ng; i++)
 *(num+i)=(int *) malloc (Ng*sizeof(int));
 
 printf("Vvedite massy gruzov:\n");
 for(i=0;i<Ng;i++)
 {
 printf("Vvedite massu %d-go gruza:\n",i+1);
 scanf("%d",a+i);
 }
 s=0;
 clrscr();
 for(i=0;i<Ng;i++)
 {
  if(gruz>*(a+i))
  {
   z=0;
   s=*(a+i);
   *(*(max)+i)=*(a+i);
   *(*(num+i)+z)=i;
   *(*(max+1)+i)=z;
   z++;
   for(j=0;j<Ng;j++)
   {
    if(i!=j)
    {
     if(gruz>=(s+*(a+j)))
     {
      s+=*(a+j);
      *(*(num+i)+z)=j;
      *(*(max+1)+i)=z;
      z++;
     }
     else
     {
      temp=s+*(a+j)-gruz;
      for(k=0;k<*(*(max+1)+i);k++)
      {
       if(*(a+*(*(num+i)+k))<*(a+j) && *(a+*(*(num+i)+k))>=temp)
       {
    s=s-*(a+*(*(num+i)+k));
    *(*(num+i)+k)=j;
    s=s+*(a+j);
       }
      }
     }
     if(s>*(*(max)+i) && gruz>=s) *(*(max)+i)=s;
    }
   }
  }
 }
 maxi=*(*(max));
 *(*(max+2))=0;
 for(i=0;i<Ng;i++)
 {
  if(*(*(max)+i)>maxi)
  maxi=*(*(max)+i);
 }
 for(i=0;i<Ng;i++)
 {
  if(*(*(max)+i)==maxi)
  {
   *(*(max+2)+(*(*(max+2))+1))=i;
   *(*(max+2))++;
  }
 }
 for(i=0;i<*(*(max+2));i++)
 {
  printf("\nmax[%d]=%d\nnushno zagrushat' eti gruzi:",i,*(*(max)+(*(*(max+2)+(i+1))))
);
  for(j=0;j<(*(*(max)+(*(*(max+2)+(i+1))))+1);j++)
  printf("%d ",*(*(num+ *(*(max+2)+(i+1)))+j));
 }
 getch();
}

Автор: Oleg_Ci 30.7.2006, 10:13

В массивах max и num всякая галиматья находится, я процедуру вывода содержимого массивов сделал, и вызываю из разных участков программы.
А программу не на Ci, а на С++ нельзя-было писать ?

Код


#include <conio.h>
#include <stdio.h>
#include <alloc.h>
#include <stdlib.h>

#include <iostream>
using std::cout;
using std::endl;

  int i,j,k,s,z,temp,gruz,maxi,Ng;
  int* a;
  int** max;
  int** num;


void Write(int writ)
{
  // вывод содержимого массивов
  cout<<"Number > "<<writ<<endl<<endl;  writ++; // номер "вывода"

  cout<<" max > ";
  for (i=0; i<Ng; i++)
    for (j=0; j<4; j++)
      cout<<max[i][j]<<" ";

  cout<<endl<<endl<<" num > ";
  for (i=0; i<Ng; i++)
    for (j=0; j<Ng; j++)
      cout<<num[i][j]<<" ";

  cout<<endl<<endl<<" a > ";
  for (i=0; i<Ng; i++)
    cout<<*(a+i)<<" ";

  cout<<endl<<endl;
  system("pause");
  clrscr();
}

void main(){
 
 printf("Vvedite gruzopod'emnost': ");    // грузоподъёмность
 scanf("%d",&gruz);
 printf("Vvedite kolichestvo gruzov:\n");     // кол-во грузов
 scanf("%d",&Ng);    

// выделение памяти
 a=(int*) malloc (Ng*sizeof(int));
    
 max=(int **) malloc (Ng*sizeof(int*));
 for (i=0; i<Ng; i++)
 *(max+i)=(int *) malloc (4*sizeof(int));    //
    
 num=(int**) malloc (Ng*sizeof(int *));    
 for (i=0; i<Ng; i++)
 *(num+i)=(int *) malloc (Ng*sizeof(int)); //

 printf("Vvedite massy gruzov:\n");
 for(i=0;i<Ng;i++)
 {    
  printf("Vvedite massu %d-go gruza:\n",i+1);
  scanf("%d",a+i);
 }
 s=0;    
 clrscr();
 Write(1);   // <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<1
 for(i=0;i<Ng;i++)
 {    
  if(gruz>*(a+i))
  {
   z=0;
   s=*(a+i);    
   *(*(max)+i)=*(a+i);
   *(*(num+i)+z)=i;
   *(*(max+1)+i)=z;
   z++;
   Write(2);   // <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<2
   for(j=0;j<Ng;j++)
   {
    if(i!=j)
    {    
     if(gruz>=(s+*(a+j)))
     {
      s+=*(a+j);    
      *(*(num+i)+z)=j;    
      *(*(max+1)+i)=z;
      z++;
     } // end if
     else    
     {
      temp=s+*(a+j)-gruz;    
      for(k=0;k<*(*(max+1)+i);k++)
      {    
       if(*(a+*(*(num+i)+k))<*(a+j) && *(a+*(*(num+i)+k))>=temp)// здесь останавливается
       {    
    s=s-*(a+*(*(num+i)+k));    
    *(*(num+i)+k)=j;
    s=s+*(a+j);    
       }    // end if
      }      // end for k
     }     // end if(gruz>=(s+*(a+j))) - else
     if(s>*(*(max)+i) && gruz>=s) *(*(max)+i)=s;
    }     // end if(i!=j)
   }     // end for(j=0;j<Ng;j++)
  }      // end if(gruz>*(a+i))
 }     // end for(i=0;i<Ng;i++)
 maxi=*(*(max));
 *(*(max+2))=0;
 Write(3);   // <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<3
 for(i=0;i<Ng;i++)
 {    
  if(*(*(max)+i)>maxi)
  maxi=*(*(max)+i);    
 }
 Write(4);   // <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<4
 for(i=0;i<Ng;i++)    
 {
  if(*(*(max)+i)==maxi)    
  {    
   *(*(max+2)+(*(*(max+2))+1))=i;    
   *(*(max+2))++;    
  }
 }
 Write(5);   // <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<5
 for(i=0;i<*(*(max+2));i++)
 {    
  printf("\nmax[%d]=%d\nnushno zagrushat' eti gruzi:",i,*(*(max)+(*(*(max+2)+(i+1)))));
  int x = (*(*(max)+(*(*(max+2)+(i+1))))+1);
  for(j=0;j<x;j++)
    printf("%d ",*(*(num+ *(*(max+2)+(i+1)))+j));// здесь останавливается программа
 }    
 getch();
}

Автор: ptr 30.7.2006, 10:38

Просто ужас smile

. За те пять минут, которые я смотрел код, я понял лишь одно - в коде я не понял ничего абсолютно. Kot, ты бы хоть прокомментировал программу что ли. А то разбираться что есть, например, вот это (*(*(max)+(*(*(max+2)+(i+1))))+1) как то особого желания не возникает.

Автор: Oleg_Ci 30.7.2006, 10:53

И вообще ты помойму слишком "намудрил". Я сочинил программу, она выводит на консоль процент загрузки грузовика, посмотри ведь всё проще можно сделать smile

Код


#include <stdlib.h>
#include <iostream>
using namespace std;

void main()
{
  int gruz; // грузоподъёмность грузовика
  int ng;   // количество грузов
  int *mas; // массив для масс груза
  cout<<"Vvedite gruzopod'emnost': ";
  cin>>gruz;
  cout<<"Vvedite kolichestvo gruzov: ";
  cin>>ng;
  mas = new int[ng];
// вводим массу груза
  for ( int i=0; i<ng; i++ )
  {
    cout<<"Vvedite massu gruza "<<i+1<<" : ";
    cin>>mas[i];
  }
  cout<<endl;
/////////// выводим процент загрузки грузовика ////////////
  for( int i=0; i<ng; i++ )
    cout<<"Number gruz "<<i<<" zagruzka  "<<100*mas[i]/gruz<<" %"<<endl;

  delete [] mas;
  cout<<endl<<endl;
  system("pause");
}

Автор: apook 30.7.2006, 12:16

Kot и впрямь перемудрил, а вообше как я понял цель задачи написать
алгоритм подбора наиболее удачной комбинации грузов которые надо уб
рать и соответственно оставить . По ходу это надо долго думать
Вот очень грубый вариант такого алгоритма(код Kot-а я так и не разобрал
но там что-то подобное

Код


#include <conio.h>
#include <stdio.h>
#include <alloc.h>
//#include <stdlib.h>

void main()
{
int i, n, _overload=0, loading=0, tonnage, Ng, **array;


printf("Введите грузоподьемность: ");
scanf("%d", &tonnage);

printf("Введите количество грузов: ");
scanf("%d", &Ng);

array = (int **) malloc (Ng * sizeof(int*));

printf("\t-- Введите массу грузов --\n");

for(i=0; i < Ng; i++)
     {
      array[i] = (int *) malloc (sizeof(int));
      printf("\t%5s%2d-го %s: ", "масса", i+1, "груза");
      scanf("%d", &array[i][0]);
      loading = loading + array[i][0];
          }

/*etot algoritm yavno nado uluchshat'*/

printf("\n%5s%2d%13s%3d", "Грузоподьемность", tonnage, "Загружено", loading);
if ((_overload = (loading - tonnage)) > 0)
     {
      printf("%13s%3d\n", "Перегруз", _overload);
      i=0;
      while (i < Ng && _overload > 0)  
           {
            if (array[i][0] == _overload)
                 { 
                  printf("Убрали груз N- %d  массой = %d\n", i+1, array[i][0]); //точное совпадение
                  array[i][0] = 0;
                  _overload = _overload - array[i][0];
                      }
            else if (array[i][0] < _overload)
                 {
                  _overload = _overload - array[i][0];
                  printf("Убрали груз N- %d  массой = %d\n", i+1, array[i][0]);
                  array[i][0] = 0;
                  _overload = _overload - array[i][0];
                      }
            i++;
                }
           }
else
     {
      printf("\nЗагруженный груз соответствует грузоподьемности\n", _overload);
          }

// - - - - - -- обработка результата - - - -- - 
printf("\n"); 
i=0;
loading=0;
while (i < Ng)
     {
      if (array[i][0] != 0)
           {
            loading = loading + array[i][0];
            printf("Грузим груз № %d  массой = %d\n", i+1, array[i][0]);
                }
      i++;
          }

if (loading < tonnage) printf ("\nНесоответствие состовляет минус %d\n", tonnage - loading);
else if (loading > tonnage) printf ("\nНесоответствие состовляет плюс %d\n", loading - tonnage);
getch();
     }

)

Автор: apook 30.7.2006, 16:59

Вот мой код усовершенствованный Можно очень наворотить но не лучше ли просто не допустить перегрузку на стадии загрузки тогда код будет меньше в раза четыре

Код


#include <conio.h>
#include <stdio.h>
#include <alloc.h>

void main()
{
int i, c, n, j, _overload=0, loading=0, tonnage, Ng, **array;


printf("Введите грузоподьемность: ");
scanf("%d", &tonnage);

printf("Введите количество грузов: ");
scanf("%d", &Ng);

array = (int **) malloc (Ng * sizeof(int*));

printf("\t-- Введите массу грузов --\n");

for(i=0; i < Ng; i++)
     {
      array[i] = (int *) malloc (sizeof(int));
      printf("\t%5s%2d-го %s: ", "масса", i+1, "груза");
      scanf("%d", &array[i][0]);
      loading = loading + array[i][0];
          }

/*etot algoritm yavno nado uluchshat'*/

printf("\n%5s%2d%13s%3d", "Грузоподьемность", tonnage, "Загружено", loading);

if ((_overload = (loading - tonnage)) > 0)
     {
      printf("%13s%3d\n", "Перегруз", _overload);

      /*Какой груз будем убирать?*/
      for (i=0; i < Ng; i++)
           { //начало 4-х ступенчатой проверки на удачные комбинации
            if ((array[i][0] != 0 && array[c][0] != 0) && (array[i][0] == _overload)) //1
                 {//ищем точное попадание...
                  _overload = _overload - (array[i][0]);
                  printf("Убрали %d-ый =[%d] груз\n", i+1, array[i][0]); 
                  array[i][0] = 0;
                      }
 
            for (c=0; c < Ng; c++) //2
                 { //пошли варианты n-ый + n-ый
                  if ((array[i][0] != 0 && array[c][0] != 0) && (c != i) && (array[c][0] <= _overload - array[c][0]) && 
                       ((array[i][0] + array[c][0]) == _overload))
                       { //принимается первый удачный
                        _overload = _overload - (array[i][0] + array[c][0]);
                        printf("Убрали %d-ый + %d-ый =[%d] груз\n", i+1, c+1, array[i][0] + array[c][0]);
                        array[i][0] = 0;
                        array[c][0] = 0;
                            }
                      }

            for (c=0; c < Ng; c++) //3
                 { //пошли варианты n-ый + n-ый + n-ый 
                  for (n=0; n < Ng; n++)
                       {
                        if ((array[i][0] != 0 && array[c][0] != 0 && array[n][0] != 0) && 
                            (c != i && c != n && i != n) &&
                            (array[c][0] <= (_overload - (array[c][0] + array[n][0]))) && 
                            ((array[i][0] + array[c][0] + array[n][0]) == _overload))
                             { //принимается первый удачный
                              _overload = _overload - (array[i][0] + array[c][0] + array[n][0]);
                              printf("Убрали %d-ый + %d-ый + %d-ый =[%d] груз\n", i+1, c+1, n+1, array[i][0] + array[c][0] + array[n][0]);
                              array[i][0] = 0;
                              array[c][0] = 0;
                              array[n][0] = 0;
                                  }
                            }
                      }

            for (c=0; c < Ng; c++) //4
                 {
                  for (n=0; n < Ng; n++)
                       {
                        for (j=0; j < Ng; j++)
                             {//пошли варианты n-ый + n-ый + n-ый + n-ый 
                              if ((array[i][0] != 0 && array[c][0] != 0 && array[n][0] != 0 && array[j][0] != 0) &&
                                  (c != i && c != n && c != j && i != n && i != j && n !=j) &&
                                  (array[c][0] <= (_overload - (array[c][0] + array[n][0]+ array[j][0]))) && 
                                  ((array[i][0] + array[c][0] + array[n][0] + array[j][0]) == _overload))
                                   { //принимается первый удачный
                                    _overload = _overload - (array[i][0] + array[c][0] + array[n][0] + array[j][0]);
                                    printf("Убрали %d-ый + %d-ый + %d-ый + %d-ый =[%d] груз\n", i+1, c+1, n+1, j+1, array[i][0] + array[c][0] + array[n][0] + array[j][0]);
                                    array[i][0] = 0;
                                    array[c][0] = 0;
                                    array[n][0] = 0;
                                    array[j][0] = 0;
                                        }
                                  }
                            }
                      }
                }//конец 4-х ступенчатой проверки на удачные комбинации
            printf("---------+---------\n");
           }
else
     {
      printf("\nЗагруженный груз соответствует грузоподьемности\n", _overload);
          }

// - - - - - -- обработка результата - - - -- - 
printf("\n"); 
i=0;
loading=0;
while (i < Ng)
     {
      if (array[i][0] != 0)
           {
            loading = loading + array[i][0];
            printf("Грузим груз № %d  массой = %d\n", i+1, array[i][0]);
                }
      i++;
          }
printf("\nВ общем %20d\n", loading);

if (loading < tonnage) printf ("\nНесоответствие состовляет минус %d\n", tonnage - loading);
else if (loading > tonnage) printf ("\nНесоответствие состовляет плюс %d\n", loading - tonnage);
getch();
     }

вводи побольше грузоподьемность и кол-во грузов а то может не сработать (однако слишком большие числа тоже глючат)

Автор: Oleg_Ci 30.7.2006, 17:16

Цитата(Kot @ 30.7.2006, 01:03

)

Найти номера грузов, которые необходимо оставить, чтобы грузовик был нагружен максимально.

Кстати, что понимается под нагружен максимально ? может 100% или более 90% "загруженности" , есть ли конкретное значение максимального ???

Автор: apook 30.7.2006, 17:20

Максимально ты вводиш сам

Код


 printf("Vvedite gruzopod'emnost': ");
 scanf("%d",&gruz);

Автор: Oleg_Ci 30.7.2006, 17:28

Цитата(apook @ 30.7.2006, 21:20

)

Максимально ты вводиш сам

Это грузоподъёмность грузовика. А надо другое. smile

Допустим грузоподъёмность равна 100 (тонн), а вес груза равен скажем 98 (тонн), и что теперь? грузовик нагружен максимально ? или немаксимально ?

Автор: apook 30.7.2006, 18:06

Получется недогруз, что не является ошибкой. Если вес 1-го груза равен
98 а второго 9 какой бы грузчик выбрал груз? Он наверно не стал бы
отпиливать от второго груза 2(кг или тонны) Хотя и такое возиожно.

Автор: Oleg_Ci 30.7.2006, 18:29

Цитата(apook @ 30.7.2006, 22:06

)

Получется недогруз, что не является ошибкой.

Тогда как вычислить ошибку, я так понимаю что если груз больше грузоподъёмности - это ошибка, а когда груз меньше - где ошибка ? Нужно число (или процент) которое будет считаться нормальным, скажем это число - 90%, если груз меньше то ситуация считается НЕнагружен максимально, ну если больше то - нагружен максимально. Вот я и хотел узнать у Kot'а что считать нагружен максимально ? помойму его вводить надо самому, а тогда задача проще простого, я пример приводил, скажем расчитывает он у меня загруженность грузовика, в процентах, вот берём эти проценты, и отбрасываем не нужный груз, который не входит в предел скажем от 90% до 100%.А если слишком маленький, то новерно складывать их надо в один грузовик по нескольку грузов.(вот здесь загвозка возможна), хотя надо-ли это? Сейчас если постараюсь то напишу программу, правда на С++.

Автор: Oleg_Ci 30.7.2006, 20:34

Корче тоже сделал программу, только слишком маленькие "грузы", не складывает в один грузовик. Короче я спaть пошёл...

Код


#include<iostream>
#include<cstdlib>
#include <windows.h>
using namespace std;

char b[100];
char* ru( char *ch )
{
    b[1] = '\0';
    AnsiToOem( ch, b );
    return b;
}

void main()    
{
    const int norma = 90; /* 90% - это число "нормальности загруженности", если груз нагружает грузовик
                          меньше чем на 90% то НЕДОГРУЗКА, если от 90% до 100% 
                          то грузовик был нагружен максимально, ну а если более 100% то перегрузка */
  int gruz;    // грузоподъёмность грузовика    
  int ng;        // количество грузов
  int *mas;    // массив для масс груза
  int pt_min; //  грузы попадающих под категорию НЕДОГРУЗКА
  int pt_max; //  грузы - перегрузки

        // вводим значения
  cout<<ru("Введите грузоподъёмность > ");    
  cin>>gruz;                // грузоподъёмность
  cout<<ru("Введите количество грузов > ");;    
  cin>>ng;                //  количество грузов
  mas = new int[ng];
        // вводим массу груза    
  for ( int i=0; i<ng; i++ )    
  {    
    cout<<ru("Введите массу груза  ")<<i+1<<" : ";    
    cin>>mas[i];    
  }    
  cout<<endl;    

  // сортируем грузы
    for ( int i = 0; i<ng-1; i++ )
        if ( mas[i]>mas[i+1] )
        {
            int x = mas[i];
            mas[i] = mas[i+1];
            mas[i+1] = x;
            if (( i -=2)<0 ) i=-1;
        };

////////////////////////////////////////////////////////////////////////
///////////////////////  загрузкa грузовика ////////////////////////
  for ( pt_min = 0; 100*mas[pt_min]/gruz <= norma  && pt_min < ng; pt_min++ );
  for ( pt_max = pt_min; 100*mas[pt_max]/gruz <= 100 && pt_max < ng; pt_max++ );
/* теперь в массиве от 0 до pt_min - недогрузки, от pt_min до pt_max - нормальный груз
    от pt_max до ng - перегрузки  */

//// выводим результаты  //////////////////////////
    for ( int i=0; i<ng; i++ )
    {
        cout<<ru("Груз номер ")<<i+1;
        cout<<ru("  массой  ")<<mas[i];
        if ( i < pt_min ) cout<<ru("  недогружает грузовик")<<endl;
        else if ( i <pt_max ) cout<<ru("  нагружает грузовик максимально")<<endl;
        else cout<<ru("  больше чем может увезти грузовик")<<endl;
    };
/////////  складываем "маленькие" грузы в один грузовик по нескольку грузов  ///
////// я недоделал...

  delete [] mas;    
  cout<<endl<<endl;    
  system("pause");    
}

Автор: Kot 30.7.2006, 22:59

Условия таковы, что, если сумма масс всех введенных грузов не превышает грузоподъемность, то надо оставлять все грузы, если нет - искать максимальную сумму масс каких-либо грузов из введенных, причем эта сумма не должна превышать грузоподъемность. На экран вывести номера грузов, которые надо оставить. Например:
Грузоподъемность=87;
1-й груз = 31
2-й груз = 7
3-й груз = 12
4-й груз = 3
5-й груз = 45
Оставить грузы №: 1, 2, 4, 5
Задачу желательно написать на Си.

Автор: zkv 31.7.2006, 03:51

есть рекурсивный вариант, правда в основном на С++, но ведь главное алгоритм, а переделать недолго. на работоспособность особо не проверял, но в общем случае работает правильно
над тем какие переменные должны быть глобальными а какие нет, не задумывался
но в рекурсивную функцию лучше лишнего не пихать

Код


#include <iostream>
using namespace std;
bool     *pbTmpFlags, //для перебора всех вариантов 
         *pbResFlags; //для результата
unsigned n;
float     fGruzopod, *pfGruz, fTmpSum=0, fMaxSum=0;

bool Sum()
{
    fTmpSum=0;
    for(unsigned i=0; i<n; i++)
        if( pbTmpFlags[i] )
            fTmpSum+=pfGruz[i];
    if( fTmpSum <= fGruzopod )//не тяжело для грузовика
    {
        if( fTmpSum > fMaxSum)//но больше предыдущего варианта
        {
            memcpy(pbResFlags, pbTmpFlags, n);    //ничего лучше не придумал
            fMaxSum=fTmpSum;            
        }
        return true;
    }
    return false;
}
unsigned GetLast()            //возвращает номер последнего добавленного груза
{
    for(unsigned i=n-1; i>0; i--)
        if( pbTmpFlags[i] )
            return i;
    if(pbTmpFlags[0])
        return 0;
    else
        return n;
}

void Gruzchik( unsigned i )        //рекурсивная функция то загружает то разгружает
{
    if(i==n)                
    {                        //дошли до конца
        i=GetLast();        //ищем последний загруженный
        if(i==n)            
            return;            //выход когда все перебрали
        pbTmpFlags[i] = !pbTmpFlags[i];//убираем его с грузовика
        Gruzchik(i+1);                           //пробуем следующий
    }
    else
    {
        pbTmpFlags[i] = !pbTmpFlags[i];        //ставим на грузовик
        if( Sum() )                            //взвешиваем грузовик
            Gruzchik( i+1 );                //если не тяжело то за следующим
        else                                
        {                                            //а если тяжко
            pbTmpFlags[i] = !pbTmpFlags[i];            //снимаем обратно 
            Gruzchik(i+1);                            //и за следующим
        }
    }
}
main()
{
    cout<<"\nMax ves :";
    cin>>fGruzopod;
    cout<<"\nKol-vo gruzov:";
    cin>>n;
    pfGruz = new float[n];     // тут должны быть
    pbTmpFlags = new bool[n];// всякие
    pbResFlags = new bool[n];// проверки
    cout<<"\nGruzi:";
    unsigned FirstGood=n;
    for(unsigned i=0; i<n; i++)
    {
        cin>>pfGruz[i];
        if( (FirstGood==n) && (pfGruz[i]<=fGruzopod) )
        {
            FirstGood=i;
            pbTmpFlags[i]=true;
            pbResFlags[i]=true;
        }
        else
        {
            pbTmpFlags[i]=false;
            pbResFlags[i]=false;
        }
    }
    if( FirstGood==n )
    {
        cout<<"Vse bolshe maximuma";
        return 0;
    }
    fMaxSum=pfGruz[FirstGood];
    Gruzchik( FirstGood+1 );
    cout<<"\notvet: \n";
    for(i=0; i<n; i++)
        if(pbResFlags[i])
            cout<<i+1<<"-iy gruz = "<<pfGruz[i]<<endl;
    cout<<"Obshiy ves:"<<fMaxSum;
    cin.ignore();//просто 
    cin.get();     //задержка
    if(pfGruz)
        delete[]pfGruz;
    if(pbTmpFlags)
        delete[]pbTmpFlags;
    if(pbResFlags)
        delete[]pbResFlags;
}

Автор: apook 31.7.2006, 15:20

Данная программа справляется с поставленной задачей (Прямо подбор паролей)

Код


#include "conio.h"
#include "iostream.h"
#include "iomanip.h"



int step(int *array[], int Ng, int _overload)
{
int i, c, n, j, o, rez;

/*Какой груз будем убирать?*/

for (i=0, rez=0; i < Ng; i++)
     {
      if ((array[i][0] != 0) && (array[i][0] == _overload)) //step from step 1
           {//ищем точное попадание...
             _overload = _overload - (array[i][0]);
             cout << "\nУбрали " << i+1 << "-ый  =[" << array[i][0] << "] груз\n";
             array[i][0] = 0;
             rez=1;
                }

        for (c=0; rez == 0 && c < Ng; c++) //step from step 2
            { //пошли варианты n-ый + n-ый
             if ((array[i][0] != 0 && array[c][0] != 0) && (c != i) && (array[c][0] <= _overload - array[c][0]) && 
                 ((array[i][0] + array[c][0]) == _overload))
                  { //принимается первый удачный
                   _overload = _overload - (array[i][0] + array[c][0]);
                   cout << "\nУбрали " << i+1 << "-ый + " << c+1  <<  "-ый  =[" 
                        << array[i][0] + array[c][0] << "] груз\n";
                   array[i][0] = 0;
                   array[c][0] = 0;
                   rez=1;
                       }
                 }

       for (c=0; rez == 0 && c < Ng; c++) //step from step 3
            { //пошли варианты n-ый + n-ый + n-ый 
             for (n=0; n < Ng; n++)
                  {
                   if ((array[i][0] != 0 && array[c][0] != 0 && array[n][0] != 0) && 
                       (c != i && c != n && i != n) &&
                       (array[i][0] <= (_overload - (array[c][0] + array[n][0]))) && 
                       ((array[i][0] + array[c][0] + array[n][0]) == _overload))
                        { //принимается первый удачный
                         _overload = _overload - (array[i][0] + array[c][0] + array[n][0]);
                         cout << "\nУбрали " << i+1 << "-ый + " << c+1  << "-ый + " << n+1 << "-ый  =[" 
                              << array[i][0] + array[c][0] + array[n][0] << "] груз\n"; 
                         array[i][0] = 0;
                         array[c][0] = 0;
                         array[n][0] = 0;
                         rez=1;
                             }
                       }
                 }

       for (c=0; rez == 0 && c < Ng; c++) //step from step 4
            {
             for (n=0; n < Ng; n++)
                  {
                   for (j=0; j < Ng; j++)
                        {//пошли варианты n-ый + n-ый + n-ый + n-ый 
                         if ((array[i][0] != 0 && array[c][0] != 0 && array[n][0] != 0 && array[j][0] != 0) &&
                             (c != i && c != n && c != j && i != n && i != j && n !=j) &&
                             (array[i][0] <= (_overload - (array[c][0] + array[n][0]+ array[j][0]))) && 
                             ((array[i][0] + array[c][0] + array[n][0] + array[j][0]) == _overload))
                              { //принимается первый удачный
                               _overload = _overload - (array[i][0] + array[c][0] + array[n][0] + array[j][0]);
                               cout << "\nУбрали " << i+1 << "-ый + " << c+1  << "-ый + " << n+1 << "-ый + " << j+1
                                    << "-ый  =[" << array[i][0] + array[c][0] + array[n][0] + array[j][0] << "] груз\n"; 
                               array[i][0] = 0;
                               array[c][0] = 0;
                               array[n][0] = 0;
                               array[j][0] = 0;
                               rez=1;
                                    }
                             }
                       }
                 }

       for (c=0; rez == 0 && c < Ng; c++) //step from step 5
            {
             for (n=0; n < Ng; n++)
                  {
                   for (j=0; j < Ng; j++)
                        {
                         for (o=0; o < Ng; o++)
                              {//пошли варианты n-ый + n-ый + n-ый + n-ый + n-ый 
                               if ((array[i][0] != 0 && array[c][0] != 0 && array[n][0] != 0 && array[j][0] != 0 && array[o][0] != 0) &&
                                   (c != i && c != n && c != j && c != o && i != n && i != j && i != o && n != j && n != o && o != j) &&
                                   (array[i][0] <= (_overload - (array[c][0] + array[n][0] + array[j][0] + array[o][0]))) && 
                                   ((array[i][0] + array[c][0] + array[n][0] + array[j][0] + array[o][0]) == _overload))
                                    { //принимается первый удачный
                                     _overload = _overload - (array[i][0] + array[c][0] + array[n][0] + array[j][0] + array[o][0]);
                                     cout << "\nУбрали " << i+1 << "-ый + " << c+1  << "-ый + " << n+1 << "-ый + " << j+1 << "-ый + "
                                          << o+1 << "-ый  =[" << array[i][0] + array[c][0] + array[n][0] + array[j][0] + array[o][0]
                                          << "] груз\n"; 
                                     array[i][0] = 0;
                                     array[c][0] = 0;
                                     array[n][0] = 0;
                                     array[j][0] = 0;
                                     array[o][0] = 0;
                                     rez=1;
                                         }
                                   }
                             }
                       }
                 }

          } //
return _overload;
     }    


void main()
{
int i, c, n, j, _overload=0, shift_overload, tonnage, loading=0, Ng;

cout << "Введите грузоподьемность: ";
cin >> tonnage;

NgLabl:
cout << "Введите количество грузов: ";
cin >> Ng;
if (Ng > 30 || Ng <= 0)
     { //Ограничим 30-ю ато будет медленно работать(а то и зависнет) 
      Ng=0;
      cout << "Введите от 1-го до 30-и\n";
      goto NgLabl;
          }
int **array = new int*[Ng];
cout << "\t-- Введите массу грузов --\n";

for(i=0; i < Ng; i++)
     {
      array[i] = new int[1];
      cout << "\t" << setw(5) << "масса" << setw(2) << i+1 << "-го" << " груза "; 
      cin >> array[i][0];
      loading = loading + array[i][0];
          }

/*etot algoritm escho nado uluchshat'*/

cout << "\n" << setw(5) << "Грузоподьемность" << setw(3) << tonnage << setw(13)
     << "Загружено" << setw(3) << loading;

if ((_overload = (loading - tonnage)) > 0)
     {
      cout << setw(13) << "Перегруз" << setw(3) << _overload << "\n";
      shift_overload = _overload;
//-- - - - - - -- - - - - -- - - - - - -- - - - - - -- - - -
for (c=0; c <= 5; c++) //steps
     {
      for (i=0; ; i++)
           {
            if ((shift_overload = step(array, Ng, shift_overload)) != 0)
                 {
                  cout << " . ";
                  shift_overload--;
                      }
            else break;
                }
      if (i != 0)  shift_overload = i;
          }
//-- - - - - - -- - - - - -- - - - - - -- - - - - - -- - - -
cout << "\n";
          }

else
     {
      cout << "\nЗагруженный груз соответствует грузоподьемности\n";
          }
// - - - - - -- обработка результата - - - -- - 
i=0;
loading=0;



while (i < Ng)
     {
      if ((array[i][0] != 0) && (array[i][0] <= tonnage))
           {
            if ((loading + array[i][0]) <= tonnage)
                 {  
                  loading = loading + array[i][0];
                  cout << "Грузим груз № " << i+1 << " массой = " << array[i][0] << "\n";
                      }
                }
      i++;
          }

delete array;

cout << "\nВ общем" << setw(20) << loading << "\n";
cout << "\nTonnage = " << tonnage << "\n";
getch();

     if (loading < tonnage)
          {         
           cout << "\nНесоответствие состовляет минус " << tonnage - loading << "\n";
               }
     else if (loading > tonnage)
          { 
           cout << "\nНесоответствие состовляет плюс " << loading - tonnage << "\n";
               }

cout << "\nPress any key To Exit ";
getch();
cout << "\r                     \r";
     }