Задача о рюкзаке - История изменений

Logic-samara в 12:51, 29 сентября 2016

2016-09-29T12:51:03Z

Logic-samara в 17:56, 2 февраля 2016

2016-02-02T17:56:08Z

Logic-samara в 05:16, 14 января 2016

2016-01-14T05:16:49Z

Logic-samara в 05:48, 16 ноября 2015

2015-11-16T05:48:58Z

Ws: Восстановление статей Logic-samara

2015-11-15T15:06:02Z

Восстановление статей Logic-samara

Новая страница

[[файл:ЗР01.JPG|thumb|300|[[Математическая модель]] ЗР]]
== Определение ==
'''Задача о рюкзаке''' — это [[задача целочисленного программирования]] о загрузке заданного объёма (веса) предметами наибольшей стоимости (полезности).

== Постановка задачи ==
Имеется '''n''' видов предметов (грузов) и рюкзак ёмкостью (грузовместимостью, грузоподъёмностью) '''b'''. Пусть заданы объём (вес) '''aj''' и стоимость (полезность) '''cj''' для '''j'''-ого предмета, '''j=1,2,…,n'''. Необходимо определить вариант загрузки с максимальной стоимостью.

Задача о рюкзаке (ЗР) формулируется следующим образом:

[[файл:ЗР01.JPG]]

или

[[файл:ЗР02.JPG]],

где '''xj''' — количество предметов '''j'''-го вида, '''j=1,2,…,n'''.

Задача о рюкзаке относится к целочисленному программированию. Для решения задачи о рюкзаке применяется метод динамического программирования.

== Алгоритм решения ==
Входные данные: ''' n; b; {a1,a2,...,an}; {c1,c2,...,cn}'''.

[[файл: ЗР11.JPG]]

Выходные данные: '''L; {x1,x2,...,xn}'''.

== Задача о рюкзаке без повторений ==
При дополнительном ограничении - запрете повторений предметов - получаем задачу о рюкзаке без повторений, которая формулируется следующим образом:

[[файл:ЗР21.JPG]]

или

[[файл:ЗР22.JPG]],

где '''xj''' — означает выбор предмета '''j'''-го вида, '''j=1,2,…,n'''.

При этом алгоритм решения модифицируется в части строки 7, она меняется на строку вида:

[[файл:ЗР23.JPG]]

== Задача о рюкзаке с ограниченным числом повторений ==
При дополнительном ограничении на число повторений предметов получаем задачу о рюкзаке с ограниченным числом повторений, которая формулируется следующим образом:

[[файл:ЗР31.JPG]]

или

[[файл:ЗР32.JPG]],

где '''xj''' — количество предметов '''j'''-го вида, '''j=1,2,…,n''';

'''mj''' — число возможных повторений предметов '''j'''-го вида, '''j=1,2,…,n'''.

При этом алгоритм решения модифицируется в части строки 7, она меняется на строку вида:

[[файл:ЗР33.JPG]]

Входными данными являются: ''' n; b; {a1,a2,...,an}; {c1,c2,...,cn}; {m1,m2,...,mn}'''.

== Другие задачи: ==
*[[Каноническая задача]];
*[[Производственная задача]];
*[[Общая прямая задача линейного программирования]];
*[[Общая двойственная задача линейного программирования]];
*[[Классическая транспортная задача]];
*[[Распределительная задача]];
*[[Задача о назначениях]];
*[[Транспортная задача с промежуточными пунктами]];
*[[Трёхиндексная транспортная задача]];
*[[Задача целочисленного программирования]].

== Ссылки ==
* [[Участник:Logic-samara]]
[[Категория:Целочисленное программирование]][[Категория:Логистика]][[Категория:Алгоритмы]]

@@ Строка 54: / Строка 54: @@
 Входными данными являются: ''' n; b; {a<sub>1</sub>,a<sub>2</sub>,...,a<sub>n</sub>}; {c<sub>1</sub>,c<sub>2</sub>,...,c<sub>n</sub>}; {m<sub>1</sub>,m<sub>2</sub>,...,m<sub>n</sub>}'''.
 == Другие задачи: ==
-*[[Каноническая задача]];
+{{Список ЗМП}}
-*[[Производственная задача]];
-*[[Общая прямая задача линейного программирования]];
-*[[Общая двойственная задача линейного программирования]];
-*[[Транспортная задача]];
-*[[Распределительная задача]];
-*[[Задача о назначениях]];
-*[[Транспортная задача с промежуточными пунктами]];
-*[[Трёхиндексная транспортная задача]];
-*[[Задача целочисленного программирования]];
-*[[Задача о рюкзаке]].
 == Ссылки ==
 * [[Участник:Logic-samara]]
 [[Категория:Целочисленное программирование]][[Категория:Логистика]][[Категория:Алгоритмы]]

@@ Строка 1: / Строка 1: @@
 [[файл:ЗР01.JPG|thumb|300|[[Математическая модель]] ЗР]]
 '''Задача о рюкзаке''' — это [[задача целочисленного программирования]] о загрузке заданного объёма (веса) предметами наибольшей стоимости (полезности).
 == Постановка задачи ==
 Имеется '''n''' видов предметов (грузов) и рюкзак ёмкостью (грузовместимостью, грузоподъёмностью) '''b'''. Пусть заданы объём (вес) '''a<sub>j</sub>''' и стоимость (полезность) '''c<sub>j</sub>''' для '''j'''-ого предмета, '''j=1,2,…,n'''. Необходимо определить вариант загрузки с максимальной стоимостью.
@@ Строка 17: / Строка 15: @@
 Задача о рюкзаке относится к целочисленному программированию. Для решения задачи о рюкзаке применяется метод динамического программирования.
 == Алгоритм решения ==
 Входные данные: ''' n; b; {a<sub>1</sub>,a<sub>2</sub>,...,a<sub>n</sub>}; {c<sub>1</sub>,c<sub>2</sub>,...,c<sub>n</sub>}'''.
@@ Строка 24: / Строка 21: @@
 Выходные данные: '''L; {x<sub>1</sub>,x<sub>2</sub>,...,x<sub>n</sub>}'''.
 == Задача о рюкзаке без повторений ==
 При дополнительном ограничении - запрете повторений предметов - получаем задачу о рюкзаке без повторений, которая формулируется следующим образом:
@@ Строка 39: / Строка 35: @@
 [[файл:ЗР23.JPG]]
 == Задача о рюкзаке с ограниченным числом повторений ==
 При дополнительном ограничении на число повторений предметов получаем задачу о рюкзаке с ограниченным числом повторений, которая формулируется следующим образом:
@@ Строка 58: / Строка 53: @@
 Входными данными являются: ''' n; b; {a<sub>1</sub>,a<sub>2</sub>,...,a<sub>n</sub>}; {c<sub>1</sub>,c<sub>2</sub>,...,c<sub>n</sub>}; {m<sub>1</sub>,m<sub>2</sub>,...,m<sub>n</sub>}'''.
 == Другие задачи: ==
 *[[Каноническая задача]];
@@ Строка 70: / Строка 64: @@
 *[[Трёхиндексная транспортная задача]];
 *[[Задача целочисленного программирования]].
 == Ссылки ==
 * [[Участник:Logic-samara]]
 [[Категория:Целочисленное программирование]][[Категория:Логистика]][[Категория:Алгоритмы]]