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

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

Войти
Регистрация
Восстановить пароль
 
mobbif
0 / 0 / 0
Регистрация: 11.04.2017
Сообщений: 3
#1

Задача о ранце. Как узнать какие предметы нужно положить? - C++

11.04.2017, 23:05. Просмотров 193. Ответов 2
Метки нет (Все метки)

Как можна узнать какие предмети входять в ранец ?


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
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include <iostream>
#include <vector>
#include <limits>
 
 
using namespace std;
 
int knapsack2(const vector<int>& wts, const vector<int>& cost, int W)
{
    int k=0;
    size_t n = wts.size();
    vector<vector<int> > dp(W + 1, vector<int>(n+1, 0));
    for (size_t j = 1; j <= n; j++)
    {
        for (int w = 1; w <= W; w++)
        {
            if (wts[j-1] <= w)
            {
                dp[w][j] = max(dp[w][j - 1], dp[w - wts[j-1]][j - 1] + cost[j-1]);
 
            }
            else
            {
                dp[w][j] = dp[w][j - 1];
                
            }
            
        }
 
    }
    return dp[W][n];
}
 
void main()
{
    int W,n,K;
    setlocale(LC_ALL,"");   
    vector<int> wts;
    vector<int> cost;
    system("cls");
    cout << "Вместимость рюкзака-> ";
                        cin >> W;
                        cout << "Количество предметов-> ";
                        cin >> n;
                            system("cls");
                            wts.reserve(n); 
                            cost.reserve(n);
                        for (int i = 0; i < n; i++)
                        {   
                            int k=0, c=0;
                            K=i+1;
                            cout<<"Вес предмета № " << K<<"-> ";
                                cin >> k;
                                wts.push_back(k);
                            cout<<"Ценность предмета № " << K<<"-> ";
                                cin >> c;
                                cost.push_back(c);
                        }
 
        system("cls");
              
                cout << "Максимальная стоимость -> " << knapsack2(wts,cost,W) << endl;
 
                system("pause");
}
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
11.04.2017, 23:05
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Задача о ранце. Как узнать какие предметы нужно положить? (C++):

Определить какие студенты сдали предметы на 5 - C++
помогите создать массив записей (5 записей) студентов ФИО и их оценки по 3м предметам и определить какие студенты сдали на 5. Примерный...

Задача о ранце - C++
Всем доброго времени суток!))Очень нужна помощь...решаю задачу о ранце,метод-динамическое программирование.Нужен код-решение на С++..может...

Задача о ранце - C++
В связи с этими темами: Начало пути прогера http://www.cyberforum.ru/cpp-beginners/thread926355.html Дано: Имеется человек с...

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

Обратная задача о ранце (ДП) - C++
Здравствуйте, необходимо решить типичную задачу о ранце, в двух видах. 1. Выбрать предметы с общей максимальной ценностью при весе не...

Задача о ранце, без ценностей - C++
как решить задачу о ранце, без ценностей груза? То-есть дано число, набор цифр и операций. Нужно записать заданное число наименьшим...

2
Новичок
Модератор
1261 / 809 / 182
Регистрация: 17.07.2012
Сообщений: 4,289
Записей в блоге: 1
Завершенные тесты: 2
12.04.2017, 04:43 #2
Погуглите "Задача о ранце восстановление ответа" и скорее всего найдете ответ на свой вопрос. Если не найдете, я могу рассказать, но сейчас просто времени нет...
1
mobbif
0 / 0 / 0
Регистрация: 11.04.2017
Сообщений: 3
13.04.2017, 17:55  [ТС] #3
Нашел алгоритм на данном сайте https://neerc.ifmo.ru/wiki/index.php...EA%E7%E0%EA%E5 , но не могу реализовать в программе.

Добавлено через 19 часов 58 минут
Новичок, Нашел алгоритм на данном сайте https://neerc.ifmo.ru/wiki/index.php...EA%E7%E0%EA%E5 , но не могу реализовать в программе.
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
13.04.2017, 17:55
Привет! Вот еще темы с ответами:

Задача о ранце. Исправить ошибки в приведенном коде - C++
Кароча, трабла с кодом в указанном месте. Дебаг мне не помог... Может кто-нибудь проверить почему прерывается? #include &lt;iostream&gt; ...

Узнать, какие разряды включены в число, а какие нет - C++
Помогите разобраться.Это все надо на Си. Значение int 4 байта т.е 32 бита.Пусть есть число 10(хотя в проге число зарание не известно!!)...

Как узнать какие изменения произошли в 2 документах - C++
Добрый день! я не являюсь программистом и навыков у меня как токовых нет( Но очень нужна ваша помощь и надеюсь что нормально отнесетесь...

Как узнать, какие файлы лежат в каталоге - C++
Добрый день! Как узнать какие файлы лежат в каталоге, мне это нужно, чтобы можно было конфигурировать программу через файл настройки,...


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

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

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