Курсовая работа: Дискретное программирование
Ø задачи с разрывными целевыми функциями;
Ø задачи на несвязных и невыпуклых областях и др.
2. Задачи с неделимостями
В подавляющем большинстве случаев наличие условий неделимости определяется физическими свойствами моделируемых объектов. Так, например, они могут появиться в качестве дополнительных ограничений в уже рассматривавшейся нами выше задаче производственного планирования, если в ней осуществляется управление выпуском крупной штучной продукции.
Классическим представителем задач данного класса стала так называемая задача о ранце. Ее фабула носит достаточно условный характер и состоит в том, что солдат (или турист), собирающийся в поход, может нести груз весом не более W кг. Этот груз может состоять из набора предметов n типов, каждый предмет типа j весит wj кг и характеризуется некоторой "полезностью" uj, j < 1: n. В рамках описанной ситуации вполне естественным представляется вопрос: сколько предметов каждого вида нужно положить в ранец, чтобы его суммарная полезность была максимальной? Если в качестве компонент плана хj. принять количество укладываемых предметов типа j, то данную задачу можно записать:
Как нетрудно заметить, представленная математическая модель носит универсальный характер, и к ней могут быть сведены многие экономические задачи. Ярким подтверждением этому служит и тот факт, что в литературе она также известна как задача о загрузке судна.
2.1 ПримеркоданаязыкеJava
int knapsack(int weights[], int costs[], int needed) {
int n = weights.length;
int dp[][] = new int[needed + 1][n + 1];
for (int j = 1; j <= n; j++) {
for (int w = 1; w <= needed; w++) {
if (weights[j-1] <= w) {
dp[w][j] = Math.max(dp[w][j - 1], dp[w - weights[j-1]][j - 1] + costs[j-1]);
} else {
dp[w][j] = dp[w][j - 1];}
}
}
return dp[needed][n];
}
2.2 ПримеркоданаязыкеC#
int knapsack(int[] weights, int[] costs, int needed)
{ int n = weights.Length;
int[,] dp = new int[needed + 1, n + 1];
for (int j = 1; j <= n; j++)
{ for (int w = 1; w <= needed; w++)
{ if (weights[j - 1] <= w)
{ dp[w, j] = Math.Max(dp[w, j - 1], dp[w - weights[j - 1], j - 1] + costs[j - 1]);