С++ Многомерный ранец

Discussion in 'С/С++, C#, Rust, Swift, Go, Java, Perl, Ruby' started by lamer811, 19 Dec 2009.

  1. lamer811

    lamer811 Elder - Старейшина

    Joined:
    8 Nov 2009
    Messages:
    132
    Likes Received:
    39
    Reputations:
    12
    Всем привет
    Пытаюсь реализовать Многомерный ранец.
    Смысл в том, что у нас есть портфель (или коробка, грузовик и т.д) и нам нужно сложить в него предметы таким образом, чтобы была получена максимальная ценность предметов
    И должно быть 2 ограничения... Я сделал одномерный с одним ограничением... как добавить ещо одно?
    У меня макс. вес... Нужно например добавить ограничение по объёму

    Вот код:
    Code:
    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);
    }
    А если кто то уже сам делал на С++ поделитесь плиз