Снова о задаче с рюкзаком

24.06.2013, 18:27. Показов 800. Ответов 0

Метки нет (Все метки)

Студворк — интернет-сервис помощи студентам

Всем привет)

Осиливаю ДП, а именно задачу о рюкзаке.

Алгоритм вообщем-то понятен...кроме одного момента.

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

Зададим краевые значения функции A(s, n).

Если s = 0, то A(0, n) = 0 для всех n (ни один предмет нельзя брать, поэтому максимальная стоимость равна 0).

Если n = 0, то A(s, 0) = 0 для всех s (можно брать любые из первых s предметов, но вместимость рюкзака равна 0).

Теперь составим рекуррентное соотношение в общем случае. Необходимо из предметов с номерами 1, ..., s составить рюкзак максимальной стоимости, чей вес не превышает n. При этом возможно два случая: когда в максимальный рюкзак включен предмет с номером s и когда предмет s не попал в максимальный рюкзак.

Если предмет s не попал в максимальный рюкзак массы n, то максимальный рюкзак будет составлен только из предметов с номерами 1, ..., s - 1, следовательно, A(s, n) = A(s - 1, n).

Если же в максимальный рюкзак включен предмет s, то масса оставшихся предметов не превышает n - ws, а от добавления предмета s общая стоимость рюкзака увеличивается на ps. Значит, A(s, n) = A(s - 1, n - ws) + ps

Не понятен именно выделенный фрагмент - каков в нём смысл. Именно смысл: например когда предмет не вписывается в стоимость, то мы считаем как бэ без него "A(s - 1, n)", а когда вписывается то записываем s-1 (хотя ведь он включен в рюкзак, те по идее должно быть просто s), и (n - ws) - к чему это?

Объясните пож-ста)

ps. описание работы алгоритма брал отсюда http://informatics.mccme.ru/mo... apterid=60

cpp_developer

Эксперт

20123 / 5690 / 1417

Регистрация: 09.04.2010

Сообщений: 22,546

Блог

24.06.2013, 18:27

Ответы с готовыми решениями:

Снова хром, снова сапопроизвольно открывается, снова bkrfdf.xyz и казино
Здравствуйте! Собственно, проблема уже не новая, хотя, как показывают сообщения форума, за последние дни выскочившая у многих. Через...

Узнать плотность частиц в прямой задаче и скорость в обратной задаче в любой момент времени
Здравствуйте, Мне нужна помощь в решении простой задачи. Даже двух: прямой и обратной. Имеется начальное распределение...

Как сделать чтобы таймер дойдя до 0 стартовал снова и снова?
Здравствуйте :) Как сделать чтобы таймер дойдя до 0 стартовал снова и снова? TimerSec = 59; TimerMin = 6; for(int i = TimerSec;...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.

raxper

Эксперт

30234 / 6612 / 1498

Регистрация: 28.12.2010

Сообщений: 21,154

Блог

24.06.2013, 18:27

Помогаю со студенческими работами здесь

HP 625 снова и снова перезагружается в безопасный не заходит
Ребята помогите , проблема вот какая врубаю я ноут он доходит до заставки майкрософта и снова перезагружается в безопасный не заходит, ...

Снова ТИС и снова делемма
Привет Ребята! Имею сканер-штрих-кода, который дал дамам на склад. Представьте себе такую ситуацию: Есть ручки, которые бывают...

И снова я, и снова вылезающий установочник
Через промежутки времени вылезает установочник раньше можно было закрыть на крестик теперь он отсутствует и кнопка отмены не работает. Я...

Снова. Снова этот repaint()
Всем привет. Сколько дней уже пытаюсь, нечего не выходит. Метод repaint не срабатывает. Как я понимаю, ошибка появляется в методе redraw...

и снова .htaccess и снова rewriterule
Добрый день. Недавно столкнулся с проблемой преобразования URL, в связи с чем пришлось перерыть кучу материала по данной теме, но вопрос...

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:

Новые блоги и статьи Все статьи Все блоги /
Установка Qt Creator для C и C++: ставим среду, CMake и MinGW без фреймворка Qt 8Observer8 05.04.2026 Среду разработки Qt Creator можно установить без фреймворка Qt. Есть отдельный репозиторий для этой среды: https:/ / github. com/ qt-creator/ qt-creator, где можно скачать установщик, на вкладке Releases:. . .	AkelPad-скрипты, структуры, и немного лирики.. testuser2 05.04.2026 Такая программа, как AkelPad существует уже давно, и также давно существуют скрипты под нее. Тем не менее, прога живет, периодически что-то не спеша дополняется, улучшается. Что меня в первую очередь. . .	Отображение реквизитов в документе по условию и контроль их заполнения Maks 04.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "ПланированиеСпецтехники", разработанного в конфигурации КА2. Данный документ берёт данные из другого нетипового документа. . .	Фото всей Земли с борта корабля Orion миссии Artemis II kumehtar 04.04.2026 Это первое подобное фото сделанное человеком за 50 лет. Снимок называют новым вариантом легендарной фотографии «The Blue Marble» 1972 года, сделанной с борта корабля «Аполлон-17». Новое фото. . .
Вывод диалогового окна перед закрытием, если документ не проведён Maks 04.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "СписаниеМатериалов", разработанного в конфигурации КА2. Задача: реализовать программный контроль на предмет проведения документа. . .	Программный контроль заполнения реквизитов табличной части документа Maks 02.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "СписаниеМатериалов", разработанного в конфигурации КА2. Задача: 1. Реализовать контроль заполнения реквизита. . .	wmic не является внутренней или внешней командой Maks 02.04.2026 Решение: DISM / Online / Add-Capability / CapabilityName:WMIC~~~~ Отсюда: https:/ / winitpro. ru/ index. php/ 2025/ 02/ 14/ komanda-wmic-ne-naydena/	Программная установка даты и запрет ее изменения Maks 02.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "СписаниеМатериалов", разработанного в конфигурации КА2. Задача: при создании документов установить период списания автоматически. . .

Наверх