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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
html-profi
5 / 5 / 0
Регистрация: 25.11.2011
Сообщений: 54
#1

Помощь с алгоритмом - C++

02.05.2012, 21:51. Просмотров 302. Ответов 0
Метки нет (Все метки)

Нужно решить задачу о рюкзаке с возможностью брать любой из n предметов неограниченное количество раз. Нашел работающий алгоритм. Но он выдает только стоимость, а мне нужно чтобы он выдал еще и набор. Помогите пожалуйста.
Вот алгоритм, который нашел

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <vector>
#include <limits>
//wts - массив весов, cost - массив стоимостей предметов, W - вместимость рюкзака
//функция возвращает максимальную стоимость, которую можно набрать(решение задачи о рюкзаке
//с повторениями)
//массив dp собственно реализует динамическое программирование, описанное в статье, как K_w
int knapsack1(const std::vector<int>& wts, const std::vector<int>& cost, int W)
{
        size_t n = wts.size();
        std::vector<int> dp(W + 1);
        dp[0] = 0;
        for (int w = 1; w <= W; w++)
        {
                dp[w] = dp[w-1];
                for (size_t i = 0; i < n; i++)
                {
                        if (wts[i] <= w)
                        {
                                dp[w] = std::max(dp[w], dp[w - wts[i]] + cost[i]);
                        }
                }
        }
        return dp[W];
}
Помогите, плиз, модифицировать алгоритм, чтобы он еще и набор выводил.

Всем спасибо за помощь!
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
02.05.2012, 21:51
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Помощь с алгоритмом (C++):

Помощь с алгоритмом - C++
Начал изучать массивы и тут задание : Найти среди элементов массива значение 2 Я в целом понимаю все это,но не знаю как выглядит алгоритм...

Помогите с алгоритмом - C++
Даны координаты вершин двух трапеций. нужно проверить вложена ли одна трапеция в другую . Подскажите какую-нибудь идею, а то у меня...

Помогите с алгоритмом - C++
F(a)+2F(a+h)+2F(a+2h)+...+2F(a+(N-1)h)+F(a+Nh). При F(x)=(x^2+1)(cosx*cosx)

помогите с алгоритмом! - C++
Заполните пустые ячейки пирамиды числами так, чтобы каждое число, которое содержится в прямоугольнике, равнялось сумме чисел, расположенных...

Помогите с алгоритмом - C++
Нужно написать программу сравнения 3 чисел. Без использования массивов, функций, управляющего else. то есть только используя if

что не так с алгоритмом? - C++
пишу програму соответственно алгоритму вот код #include &lt;iostream.h&gt; #include &lt;conio.h&gt; #include &lt;string.h&gt; #include &lt;math.h&gt;...

0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
02.05.2012, 21:51
Привет! Вот еще темы с ответами:

Разобраться с алгоритмом задачи - C++
Помогите разобраться с алгоритмом, как работает программа. Я понимаю что здесь 38 перестановок. Но мне нужно знать как именно работает эта...

Кодирование алгоритмом Хаффмана - C++
Проблема - такая : Есть рабочая программа, которая кодирует текстовый файл алгоритмом хаффмана. Кодирует она двоичным кодом. Присвоение...

Не могу разобраться с алгоритмом - C++
Проанализируйте блок-схему алгоритма на рис.5. Определите, какое сообщение необходимо выводить вместо ??? На входе алгоритма: вводится...

C++, кривые Безье, Алгоритмом de Casteljau - C++
Здравствуйте, В чем собственно состоит проблема: не могу придумать как написать уравнение кривой Безье! (x(t),y(t))\=B(t) по данному набору...


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

Или воспользуйтесь поиском по форуму:
1
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru