imho.ws |
![]() |
![]() |
|
Сообщения:
Перейти к новому /
Последнее
|
Опции темы |
![]() |
# 1 |
Guest
Сообщения: n/a
|
Кто нибудь, помогите пределать прогу с С++ в Delphi. Очень нужно!!!
// Задача о рюкзаке. Решить методом динамического программирования.
#include "stdafx.h" #include "iostream" #include "iomanip" #include "fstream" #include "windows.h" #include <vector> #include "Russia.h" // Для вывода текста по-русски. если нет этой библ. то использовать iostream. using namespace std; char* Rus(LPCWSTR text); char BufRus[256]; int _tmain(int argc, _TCHAR* argv[]) { int m_bag, n; fstream File; File.open("ss.txt"); File >> m_bag >> n; // Получаем массу и количество вещей. cout << "Масса рюкзака: " << m_bag << "\t Количество вещей: " << n << endl << endl; vector< vector<int> > thing; thing.resize(n); for(int i = 0; i < n; i++) { thing[i].resize(2); File >> thing[i][0] >> thing[i][1]; // Заносим в массив массу и стоимость вещей. cout << thing[i][0] << setw(3) << thing[i][1] << endl; } // Создаем таблицу весов сумки vector< vector<int> > bag; bag.resize(n+1); for(int i = 0; i <= n; i++) bag[i].resize(m_bag+1); // Занулять таблицу не обязательно т. к. используем vector. // заносим в таблицу веса. см. сайт. for(int i = 1; i <= n; i++) { for(int j = 1; j <= m_bag; j++) if(thing[i-1][0] <= j) { for(int k = i; k < n+1; k++) if(bag[k][j] < thing[i-1][1] + bag[i-1][j-thing[i-1][0]]) bag[k][j] = thing[i-1][1] + bag[i-1][j-thing[i-1][0]]; else break; } } // Восстанавливаем путь. int i = n, j = m_bag; cout << endl << "-------------------------------" << endl; cout << "Оптимизированный рюкзак. \nДля максимальной стоимости нужно взять эти предметы:\n"; while(bag[i][j] != 0) { if(bag[i][j] == bag[i-1][j]) {i--;} else { cout << i << " "; i--; j = j - thing[i][0]; } } cout << endl; system("pause"); return 0; } |