| lamer811 |
19.12.2009 23:15 |
С++ Многомерный ранец
Всем привет
Пытаюсь реализовать Многомерный ранец.
Смысл в том, что у нас есть портфель (или коробка, грузовик и т.д) и нам нужно сложить в него предметы таким образом, чтобы была получена максимальная ценность предметов
И должно быть 2 ограничения... Я сделал одномерный с одним ограничением... как добавить ещо одно?
У меня макс. вес... Нужно например добавить ограничение по объёму
Вот код:
Код:
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);
}
А если кто то уже сам делал на С++ поделитесь плиз |
