Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
mobbif
0 / 0 / 0
Регистрация: 11.04.2017
Сообщений: 3
#1

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

11.04.2017, 23:05. Просмотров 272. Ответов 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
Ответы с готовыми решениями:

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

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

Задача о ранце
В связи с этими темами: Начало пути прогера...

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

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

2
Новичок
Модератор
1490 / 964 / 459
Регистрация: 17.07.2012
Сообщений: 4,918
Завершенные тесты: 3
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

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

Задача о ранце. Исправить ошибки в приведенном коде
Кароча, трабла с кодом в указанном месте. Дебаг мне не помог... Может...

Узнать, какие разряды включены в число, а какие нет
Помогите разобраться.Это все надо на Си. Значение int 4 байта т.е 32...


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

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

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