Форум программистов, компьютерный форум, киберфорум
Наши страницы

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

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Метод бисекции http://www.cyberforum.ru/cpp-beginners/thread608517.html
Код: #include <iostream.h> #include <float.h> #include <cmath> #include <float.h> #include <iomanip.h> float f(float x) { return x*x-4;
C++ факториал пятью способами Помогите написать пять способов нахождения факториала, число можно брать любое http://www.cyberforum.ru/cpp-beginners/thread608503.html
Глобальная переменная для хранения вещественных чисел C++
Объявите одну глобальную переменную для хранения вещественных чисел объемом 8 байт на платморфе х86 инициализируйте ее ненулевым значением и четыре глобальные переменные для хранения целых чисел в...
S(f)=x-x^3/3!+x^5/5!-x^7/7!-x^11/11!+x^13/13! C++
Вычислить: S(f)=x-x^3/3!+x^5/5!-x^7/7!-x^11/11!+x^13/13!
C++ Зачем открывать файл как бинарный? http://www.cyberforum.ru/cpp-beginners/thread608440.html
Здравствуйте! Зачем открывать файл как бинарный? Ведь от того, что мы скажем, что он бинарный, работа с ним никак не изменится!
C++ Пропала кириллица в Visual Studio Перестала сегодня выводится кириллица в Visual Studio 2010. Не могу понять в чем дело. Раньше етот код выводился без проблем#include <iostream> #include <Windows.h> using namespace std; int... подробнее

Показать сообщение отдельно
Vladimir03

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

18.06.2012, 16:12. Просмотров 3425. Ответов 2
Метки (Все метки)

И так я все сделал как вы и просили.
Условие задачи о рюкзаке:

Итак, пусть у нас есть рюкзак объёма 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++.
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru