Курсы, курсы...

[transcedentarij]

На эти выходные закончил два пятинедельных курса: "Алгоритмы" в университете Сан Диего и "Objective C" в Калифорнийском технологическом. Но, как выяснилось, это циклы из шести курсов каждый, так что - продолжаю. Признаться, я не в восторге, как их поддерживают: задать вопрос по сути некому, а когда твой проект на тесте проваливается, никаких подробностей получить не удается: "Test 12/14 failed". Это все! Иногда подробности бывают, но не часто. Когда я писал контрольную по алгоритму "Knapsack"*, я был вынужден, уйти в интеренет и посмотреть, что люди пишут, поскольку как раз в этом случае мой проект падал в одном и том же месте. Я даже создал пвраллельную тестирующую программу и провел более 1000 автоматических тестов - все нормально, а как тольку отсылаю им - не проходит. В конце концов, нашел решение у одного мужика из Ирландии. Сравнил со своим - вроде все нормально, теже ответы, но его решение проходит через курсовой тест, а мое - хоть убей. В общем, тут, видимо, дело не в том, что мое решение неправильное, а в том, что где-то я пропускал ввод неверных данных или что-то другое в таком роде. Но они при этом и не акцентировали внимание, как именно я должен поступать в случае неверных данных и т.п. Ну, в общем, сдал и ладно. Понимать - понимаю о чем идет речь, и довольно.

"Knapsack"* - одна из классических задач на алгоритмы. Допустим, у нас есть мешок, который вмещает вес N, и у нас есть ряд предметов, например - бруски из разных металлов, все разного веса и, понятно, разных стоимостей. Надо так заполнить мешок, чтобы общий вес и стоимость заложенного была максимальной. На первый взгляд все просто, но это совсем не так. Например "жадный алгоритм" тут не катит совсем.
Задача имеет вариации: бруски можно "пилить" или нельзя. Каждый брусок может быть положен один раз или несколько и т.п.