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

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

Восстановить пароль Регистрация
 
html-profi
5 / 5 / 0
Регистрация: 25.11.2011
Сообщений: 53
02.05.2012, 21:51     Помощь с алгоритмом #1
Нужно решить задачу о рюкзаке с возможностью брать любой из 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];
}
Помогите, плиз, модифицировать алгоритм, чтобы он еще и набор выводил.

Всем спасибо за помощь!
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
02.05.2012, 21:51     Помощь с алгоритмом
Посмотрите здесь:

C++ Помогите с алгоритмом
C++ что не так с алгоритмом?
помогите с алгоритмом! C++
Помогите с алгоритмом C++
C++ Помогите с алгоритмом
Помощь с алгоритмом C++
C++ Не могу разобраться с алгоритмом
Кодирование алгоритмом Хаффмана C++

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Ответ Создать тему
Опции темы

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