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

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

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Перевод строки в число http://www.cyberforum.ru/cpp-beginners/thread564030.html
У меня по заданию нужно в строку ввести числа через пробелы а потом убрать пробелы и перевести из строки в число мои цифры. #include <stdio.h> #include <stdlib.h> #include <conio.h> ...
C++ Снова о локализации Ранее было много рецептов относитьельно локализации консоли. Выведя, одну строку в поток на русском можно было, но после этого ввод в cin с последующим вводом в cout косячил. (Причем неважно какие... http://www.cyberforum.ru/cpp-beginners/thread564016.html
C++ Конструктор по умолчанию
Всем привет! Если в классе вообще нет конструктора, чем будут инициализироваться члены класса? И в чем отличие объект() и объект без скобок Заранее благодарен.
Ассоциативные контейнеры(алгоритмы)с++ C++
Создать vector<int>, считать в него список чисел из текстового файла. Выполнить, не используя циклов: поиск наибольшего значения; подсчет количества чисел, равных заданному числу; подсчет...
C++ Crypto api RC2 http://www.cyberforum.ru/cpp-beginners/thread563971.html
Доброго времени суток! Проблема такая: почему-то зашифрованные данные ничем не отличаются от исходных. В чём ошибка не понятно. #define _WIN32_WINNT 0x0400 #include <iostream> #include...
C++ Нахождение группы слов в имеющемся словаре Алгоритмы обработки символьной информации. В имеющемся словаре найти группы слов, записанных одними и теме же буквами и отличающиеся только их порядком, то есть перестановкой, например, (КОМАР,... подробнее

Показать сообщение отдельно
html-profi
5 / 5 / 0
Регистрация: 25.11.2011
Сообщений: 54

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

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