Руководство программиста программы «Задача о рюкзаке», страница 3

      }

   Goods->ColCount--;

   }

}

//---------------------------------------------------------------------------

void __fastcall TCalcWin::CalcPriceClick(TObject *Sender)

{

AnsiString s;

int *mass, *price, M, N, k, m, min, max, cnt, *f, *f1, *f2,*f3;

short i, j;

OutPut->Height = 25;

OutPut->ScrollBars = ssNone;

if ((Capacity->Text == "") || (Capacity->Text.ToInt() == 0)) //проверка наличия данных в поле Грузоподъёмность

   {

   ShowMessage("Не задана грузоподъёмность!");

   return;

   }

else

   {

   if (Capacity->Text.Length() > 4) //проверка разрядности грузоподъёмности

      {

      ShowMessage("Грузоподъёмность должна быть меньше 10000!");

      return;

      }

   }

N = Goods->ColCount - 1; //количество товаров на один меньше количества столбцов таблицы

M = Capacity->Text.ToInt(); //масса оптимального набора

mass = new int[N];

price = new int[N];

f = new int[M + 1];

f1 = new int[M + 1];

f2 = new int[M + 1];

f3 = new int[M + 1];

min = INT_MAX;

for (i = 0; i < N; i++) //заполнение массивов масс и цен товаров

   {

   if (Goods->Cells[i + 1][0].Length() < 5) //проверка разрядности масс

      {

      if ((Goods->Cells[i + 1][0] == "") || (Goods->Cells[i + 1][0].ToInt() == 0))

         {

         ShowMessage("Не задана масса " + IntToStr(i + 1) + "-го товара");

         return;

         }

      else

         mass[i] = Goods->Cells[i + 1][0].ToInt();

      }

   else

      {

      ShowMessage("Масса " + IntToStr(i + 1) + "-го товара должна быть меньше 10000!");

      return;

      }

   if (Goods->Cells[i + 1][1].Length() < 6) //проверка разрядности цен

      {

      if (Goods->Cells[i + 1][1] == "")

         {

         ShowMessage("Не задана цена " + IntToStr(i + 1) + "-го товара");

         return;

         }

      else

         price[i] = Goods->Cells[i + 1][1].ToInt();

      }

   else

      {

      ShowMessage("Цена " + IntToStr(i + 1) + "-го должна быть меньше 100000!");

      return;

      }

   if (min > mass[i]) //определение самого лёгкого товара

      min = mass[i];

   }

for (i = 0; i <= M; i++) //заполнение начальными значениями массивов выходных данных

   {

   f[i] = 0;

   f1[i] = 0;

   f2[i] = -1;

   f3[i] = 0;

   }

m = min;

while (m <= M) //пока не достигнута заданная масса набора

   {

   max = 0;

   for (i = 0; i < N; i++) //определяем цену текущего оптимального набора

      {

      k = m - mass[i]; //"извлекаем" товар из текущего оптимального набора

      if (k >= 0) //если в наборе ещё что-то есть

         if ((f[k] + price[i]) > max) //сравниваем сумму цен извлечённого товара и оставшегося набора с текущим максимумом

            { //если сумма больше максимума

            max = f[k] + price[i]; //устанавливаем новый максимум

            f1[m] = i; //запоминаем номер извлечённого товара

            f2[m] = k; //запоминаем массу оставшегося набора

            }

      }

   f[m] = max; //устанавливаем цену набора товаров для текущей массы

   m++; //увеличиваем массу на единицу

   }

m = M; //начиная с заданной массы

i = 0; //при нулевом количестве товаров в оптимальном наборе