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

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

Восстановить пароль Регистрация
Другие темы раздела
C++ Builder Переставить элементы одномерного массива в обратном порядке http://www.cyberforum.ru/cpp-beginners/thread564031.html
Переставить элементы одномерного массива в обратном порядке. Сравниваем очередной элемент со всеми последующими. { int A,i,j; randomize(); for(i=0;i<10;i++) { A=rand()%21-10; StringGrid1->Cells=A; }
C++ Перевод строки в число У меня по заданию нужно в строку ввести числа через пробелы а потом убрать пробелы и перевести из строки в число мои цифры. #include <stdio.h> #include <stdlib.h> #include <conio.h> #include <string.h> int main() { char str; long value; http://www.cyberforum.ru/cpp-beginners/thread564030.html
C++ Снова о локализации
Ранее было много рецептов относитьельно локализации консоли. Выведя, одну строку в поток на русском можно было, но после этого ввод в cin с последующим вводом в cout косячил. (Причем неважно какие потоки использовались, обычные или широкие). Мне, как то неожиданно удалось решить эту проблему, но опять же, скорее везение. Вот хотелось бы, чтобы опытные люди объяснили, почему данная программа...
C++ Конструктор по умолчанию
Всем привет! Если в классе вообще нет конструктора, чем будут инициализироваться члены класса? И в чем отличие объект() и объект без скобок Заранее благодарен.
C++ Ассоциативные контейнеры(алгоритмы)с++ http://www.cyberforum.ru/cpp-beginners/thread563977.html
Создать vector<int>, считать в него список чисел из текстового файла. Выполнить, не используя циклов: поиск наибольшего значения; подсчет количества чисел, равных заданному числу; подсчет количества чисел, удовлетворяющих условию, например, «больше, чем 15»; подсчет общего количества чисел; подсчет суммы чисел; подсчет среднего арифметического чисел. Использовать алгоритмы...
C++ Crypto api RC2 Доброго времени суток! Проблема такая: почему-то зашифрованные данные ничем не отличаются от исходных. В чём ошибка не понятно. #define _WIN32_WINNT 0x0400 #include <iostream> #include <stdlib.h> #include <fstream> #include <Windows.h> #include <WinCrypt.h> #pragma comment(lib, "advapi32.lib") подробнее

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

Всем спасибо за помощь!
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
 
Текущее время: 20:43. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru