Основная часть. 
Динамическое программирование. 
Задача о загрузке

задача алгоритм программа комбинаторный.

Способы решения задач

На практике очень часто возникают NP-полные задачи, задач о рюкзаке одна из них. Конечно надежд, на то, что для них найдется, полиномиальный алгоритм практически нет, но из этого не следует, что с задачей нельзя ничего сделать. Во первых, очень часто удается построить полиномиальный алгоритм для NP — полной задачи, конечно он даст приближенное, а не точное решение, но зато будет работать за реальное время. Во вторых, данные могут быть таковы, что экспоненциальный алгоритм, например переборный сможет работать на них разумное время. К точным методам относятся: Полный перебор, метод ветвей и границ, ДП — программирование. К приближенным: Жадные алгоритмы. Полный перебор — перебор всех вариантов (всех состояний) — малоэффективный, но точный метод. Метод ветвей и границ — по сути, сокращение полного перебора с отсечением заведомо «плохих» решений. ДП — алгоритм, основанный на принципе оптимальности Беллмана. Жадный алгоритм — основан на нахождении относительно хорошего и «дешевого» решения.

Выбор алгоритма решения задач и определение его сложности

Проанализировав перечисленные методы решения задач, выбираем динамическое программирование. Данный метод дает точное решение и выполняет все поэтапно.

В основе метода динамического программирования лежит принцип оптимальности Беллмана: «Какого бы ни было состояния системы перед очередным шагом, надо выбирать управление на этом шаге так, чтобы выигрыш на этом шаге плюс оптимальный выигрыш на всех последующих шагах был оптимальным».

Проще говоря, оптимальное решение на i шаге находится исходя из найденных ранее оптимальных решений на предшествующих шагах. Из этого следует, что для того чтобы найти оптимальное решение на последнем шаге надо сначала найти оптимальное решения для первого, затем для второго и так далее пока не пройдем все шаги до последнего.