ANTICHAT — форум по информационной безопасности, OSINT и технологиям

void __fastcall TForm1::Button1Click(TObject *Sender)
{
   // wts - массив весов, cost - массив стоимостей предметов, W - вместимость рюкзак
   
   vector<int> wts; // - вектор весов

   vector<int> cost; // - вектор - стоимостей

   int W, i; // число - вместимость

   size_t n;  // - количество предметов

   String otvet; // - ответ

    //Ввод данных
    n = StrToIntDef(Edit1->Text, 0);
    if (n == 0)
    {
        ShowMessage("Не задано количество предметов");
        exit;
    }

    // заполняем веса предметов
    for (size_t i = 1; i <= n; i++)
      wts.push_back(StrToIntDef(StringGrid1->Cells[1][i], 0));

    // заполняем стоимости предметов
    for (size_t i = 1; i <= n; i++)
      cost.push_back(StrToIntDef(StringGrid1->Cells[2][i], 0));

    W = StrToIntDef(Edit2->Text, 0);  // масса рюкзака

    if (W == 0)
    {
        ShowMessage("Не задан максимальный вес ранца");
        exit;
    }

   otvet = "В ранец необходимо поместить предметы: ";

   vector<vector<int> > dp(W + 1); // - это вектор-векторов, т.е. двойной массив

   // инициализация вектора
   for (int i = 0; i <= W; i++)
	{
		dp[i].resize(n + 1); // - изменяет количество элементов в векторе
		dp[i][0] = 0;
	}

	for (size_t i = 0; i <= n; i++)
	{
		dp[0][i] = 0; // - заполняем нулями первую строку
	}

   // - два цикла динамического программирования
	for (size_t j = 1; j <= n; j++)
	{
		for (int w = 1; w <= W; w++)
		{
			if (wts[j-1] <= w)
			{
				dp[w][j] = max(dp[w][j - 1], dp[w - wts[j-1]][j - 1] + cost[j-1]);
			} else
			{
				dp[w][j] = dp[w][j - 1];
			}
		}
	}

   otvet = "Максимальная стоимость: " + IntToStr(dp[W][n]);
   
   Memo1->Lines->Add(otvet);
}