Форум программистов, компьютерный форум CyberForum.ru

Задача о рюкзаке - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 23, средняя оценка - 4.70
Vladimir03
Сообщений: n/a
18.06.2012, 16:12     Задача о рюкзаке #1
И так я все сделал как вы и просили.
Условие задачи о рюкзаке:

Итак, пусть у нас есть рюкзак объёма W, и список из n вещей, у каждой из которых есть объём v[i] и стоимость c[i], и каждую из которых можно брать сколько угодно раз. При этом все объёмы и все стоимости будут положительными и целыми. Как же работает алгоритм?

Заведём массив max длины W+1, в котором мы по итогам работы алгоритма получим наибольшую стоимость, которую может иметь набор вещей, занимающий данный объём — для каждого объёма от 0 до W включительно.
А точнее, после k итераций мы получим для каждого объёма i max[i] — максимальную возможную стоимость набора вещей объёма i, в котором могут быть только первые k вещей.
Сразу понятно, что изначально надо инициализировать max[0] = 0. Что же остальные элементы max? Не используя никаких вещей, можно получить только набор веса 0. Значит, в max[i] (0 < i <= W) нужно записать что-то, что будет хуже, чем любая возможная стоимость набора веса i. Например, -1.
После этого надо сделать n итераций.

На k-той итерации мы делаем следующее.
До итерации в массиве в каждом элементе max[i] записана максимальная возможная стоимость набора вещей веса i, который составлен из вещей 0..k-1. Каждый раз, рассматривая элемент max[i], мы добьёмся того, чтобы там была записана максимальная возможная стоимость набора вещей веса i, который составлен из вещей 0..k. Для этого проверим, в оптимальном наборе вообще есть k-тая вещь, хотя бы одна? Если нет, то в max[i] уже записана оптимальная стоимость. Если есть, то, если из этого набора выкинуть одну k-тую вещь, то получится оптимальный набор вещей объёма i-v[k], оставленный из вещей 0..k. Но последний уже записан в max[i-v[k]]! Значит, надо просто сравнить величины max[i] и max[i-v[k]] + c[k] (если, конечно, i >= v[k]). Максимальную из них и надо записать в max[i].
Итак, после k-той итерации мы полчим в каждом max[i] наибольшую стоимость, которую может имет набор вещей, составленный из вещей. Значит, после n итераций мы получим именно то, что и обещалось. Осталось дело техники: пройтись по массиву max[i] и выбрать в нём максимальный элемент.
Как несложно заметить, ассимптотика времени работы алгоритма будет O(W*n), и используемой памяти — O(W).

Вариации:
1. Когда надо получить не только стоимость, но и сам набор.
Кроме массива max, запишем ещё и массив prev. В него мы будем записывать, какую вещь мы последний раз положили в набор. То есть, если при сравнении max[i] и max[i-v[k]] + c[k] оказалось, что max[i-v[k]] + c[k] лучше — это означает, что в оптимальном наборе веса i должен быть k-тый предмет. Таким образом, если мы выяснили, что оптимальная стоимость max[i] достигается при наборе веса i, то можно записать, что мы добавили в набор вещь prev[i]. И перейти к оптимальному набору веса i — v[prev[i]]. Там тоже посмотреть, какую вещь взяли в последний раз. И так далее, пока не дойдём до нуля.

2. Когда каждую вещь можно брать только один раз.
Тут всё ещё проще: надо просто в каждй итерации идти по массиву не снизу вверх, а сверху вниз, то есть, от W к 0. Тогда получится, что при рассмотрении max[i-v[k]], там всё ещё будет записано, набор какой максималльной стоимости веса i — v[k] можно получить, используя только вещи 0..k-1. Следовательно, если получится, что в оптимальном наборе надо использовать k-тую вещь, то она будет использована только один раз.

3. Выбор значения, как можно более близкого к данному.
Если нет стоимостей, то данный алгоритм, очевидно, помогает как можно сильнее набить рюкзак. Или же, если речь идёт не о рюкзаке, и неважно, что общий объём вещей не больше объёма рюкзака, можно из нескольких чисел с помощью сложения получить число, как можно более близкое к данному.

В всех случаях ассимптотика времени работы и используемой памяти та же.

4. Когда каждую вещь можно брать определённое количество раз.
За эту вариацию спасибо lipstick.
Есть вариация задачи, в которой вещь с номером i можно брать от 0 до q[i] раз. Конечно, можно «размножить» i-ю вещь на q[i] единиц и решить задачу о 0-1 рюкзаке. Однако, сложность такого решения будет O(W * ∑q[i]), что не очень хорошо. На самом деле, можно поступить хитрее.

Пусть q[i] = 1 + 2 + 4 + 8 +… + 2^k + r[i], где r[i] < 2^(k+1).
Тогда рассмотрим k+2 предмета объёмом 1*v[i], 2*v[i], ..., 2^k*v[i], r[i]*v[i] и стоимостью 1*c[i], 2*c[i], ..., 2^k*c[i], r[i]*c[i] соответственно.
(«Названия» новых предметов — «1 i-я вещь», «2 i-ых вещи», «4 i-ых вещи» и т. д.)

Ясно, что выбирая различные подмножества этих k+2 предметов, можно получить любое количество (от 0 до q[i]) вещей типа i. Т. е. вместо «размножения» вещей i-го типа на q[i] единиц, мы сумели ограничиться k+2 = O(log q[i]) единицами.

Такой метод будет иметь сложность порядка O(W * ∑log q[i]), что куда более эффективно, чем «наивное» решение.

Так вот погоите пожалуйста написать код на c++.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
18.06.2012, 16:12     Задача о рюкзаке
Посмотрите здесь:

C++ Задача о рюкзаке
Задача о рюкзаке C++
C++ Задача о рюкзаке
C++ Задача о рюкзаке 0-1
C++ исправьте ошибки в программе о рюкзаке
Задача о рюкзаке, решается ли она жадным алгоритмом? C++
Задача о рюкзаке. Имеются предметы, веса которых равны w1,w2,…,wn, а цены которых равны c1,c2,…,cn. Выбрать из них предметы, суммарный вес которы C++
C++ Вычислить нужную комбинацию. Задача о рюкзаке

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Denis_Aleks
0 / 0 / 0
Регистрация: 14.05.2012
Сообщений: 5
09.01.2013, 18:09     Задача о рюкзаке #2
посмотри на сайте http://algoritm-rukzaka.narod.ru/
skiff26
2 / 2 / 0
Регистрация: 15.11.2011
Сообщений: 47
04.04.2013, 06:59     Задача о рюкзаке #3
Задача о камнях (почти рюкзак) модификация)
Yandex
Объявления
04.04.2013, 06:59     Задача о рюкзаке
Ответ Создать тему
Опции темы

Текущее время: 13:42. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru