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

Задача о рюкзаке методом полного перебора. Нужно пояснение по коду - C++

22.02.2016, 20:58. Просмотров 1050. Ответов 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
#include <memory.h>
#include <iostream>
#define NINE 0x8000000
 
using namespace std;
int knapsack_r(int Wmax, int n, int *&w, int *&c, int *&m)
{
    int Cmax = NINE, Ccur = 0, iv = 0, *km = new int[n - 1], li = n - 1; //Cmax как я понимаю максимальная цена. 
    if (li > 0) //Ccur - текущая. Дальше ничего не понятно. Можете объяснить для чего нужна эта функция и что она делает?
        for (int i = 0; i* w[li] <= Wmax; i++)
        {
            if (Ccur > Cmax)
            {
                Cmax = Ccur;
                m[li] = i;
                memcpy(m, km, li* sizeof(int));
            }
}
else{
    iv = Wmax / w[li];
    Cmax = c[li]* iv;
    m[li] = iv;
}
delete[] km;
return Cmax;
}
int main() {
    int w, c, n, Wmax;
    cout << "Enter the max number\n";
    cin >> n;
    cout << "Enter the max weight\n"; 
    cin >> Wmax;           // максимальный вес рюкзака
    int *c = new int[n];   //стоимость
    int *w = new int[n];   //вес
    int *m = new int[n];   //кол-во предметов каждого типа
    cout << "Enter the cost\n";
    for(int i = 0; i < n; i++)  //присваеваем весы каждому предмету
    {
        cin >> w;
        w[i] = w;
    }
    cout << "\n";
    int maxcc = knapsack_r(Wmax, n, w, c, m);
    cout << "Number of subjects:" << n;
    cout << "\n";
    cout << "max weight:" << Wmax << endl;
    cout << "Weight of subjects";
    for (int i = 0; i < n; i++)
        cout << w[i] << " ";
    cout << "\n";
    cout << "optimal weigth of rucksack";
    int s = 0;
    for (int i = 0; i < n; i++)
        s += m[i] * w[i];
    cout << s;
    cout << "\n";
    cout << "set of subjects:";
    for (int i = 0; i < n; i++)
        cout << " " << m[i];
    cout << "\n";
    return 0;
 
}
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
22.02.2016, 20:58
Я подобрал для вас темы с готовыми решениями и ответами на вопрос Задача о рюкзаке методом полного перебора. Нужно пояснение по коду (C++):

Поиск наибольшей общей подпоследовательности методом методом полного перебора
Здравствуйте! Помогите пожалуйста с этим адом :wall: Нужно решить задачу о...

При сортировке методом полного перебора массив сбивается
Массив сбивается ровно на единицу при сортировке. Понять не могу где же. Может...

Оптимизация полного перебора
Пусть требуется подобрать пин-код длиной 4 символа (может содержать как цифры и...

Пояснение по коду
Плиз хелп с кодом, если не сложно, напишите комментарии к // Add // Remove //...

Пояснение к коду
Добрый день! Вопрос в следующем, есть конструктор объявленный в хелпе: ...

Дайте пояснение по коду
int count = 0; for (int i = 0; strok; i++) { if ((strok == 'a' &amp;&amp; strok ==...

2
_Valera_
489 / 371 / 136
Регистрация: 27.01.2015
Сообщений: 1,588
23.02.2016, 00:45 #2
Цитата Сообщение от sky123 Посмотреть сообщение
Код не мой, также в нем много ошибок.
Цитата Сообщение от sky123 Посмотреть сообщение
int w ,c, n, Wmax;
...
int *w = new int[n];
Цитата Сообщение от sky123 Посмотреть сообщение
//Cmax как я понимаю максимальная цена.
спроси у того у кого взял. Зачем давать переменным имена, если их можно назвать w, c, n , km?!
0
Mr.X
Эксперт С++
3178 / 1705 / 435
Регистрация: 03.05.2010
Сообщений: 3,867
23.02.2016, 12:34 #3
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
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
#include <algorithm>
#include <iostream>
#include <limits>
#include <utility>
#include <vector>
///////////////////////////////////////////////////////////////////////////////
typedef std::pair       < int,  int             >   T_weight_and_cost;
typedef std::vector     < T_weight_and_cost     >   T_weights_and_costs;
///////////////////////////////////////////////////////////////////////////////
void    print_most_costly_contents_of_knapsack
    (
        int                     w_capacity,
        T_weights_and_costs     weights_and_costs
    )
{
    int                     total_cost_max{};
    T_weights_and_costs     best_weights_and_costs;
 
    do
    {
        int     total_weight    {};
        int     total_cost      {};
        size_t  i               {};
 
        for( ; i < weights_and_costs.size(); ++i )
        {
            auto    &   w_c     =   weights_and_costs[i];
            total_weight        +=  w_c.first;
            total_cost          +=  w_c.second;
 
            if  (
                        total_weight
                    >   w_capacity
                )
            {
                total_cost  -=  w_c.second;
                break;
            }//if
        }//for
 
        if  (
                    total_cost
                >   total_cost_max
            )
        {
            total_cost_max  =   total_cost;
 
            best_weights_and_costs.assign
                (
                    weights_and_costs.begin     (),
                    weights_and_costs.begin     ()  +   i
                );
        }//if
    }
    while   (
                std::next_permutation
                    (
                        weights_and_costs.begin     (),
                        weights_and_costs.end       ()
                    )
            );
 
    std::cout   <<  std::endl;
 
    if  (
            best_weights_and_costs.empty()
        )
    {
        std::cout   <<  "There is no solution"
                    <<  std::endl;
    }
    else
    {
        for( auto best_w_c   :   best_weights_and_costs )
        {
            std::cout   <<  best_w_c.first
                        <<  '\t'
                        <<  best_w_c.second
                        <<  std::endl;
        }//for
    }//else
 
    std::cout   <<  "end"
                <<  std::endl;
}
///////////////////////////////////////////////////////////////////////////////
int     main()
{
    std::cout   <<  "Knapsack weight capacity: ";
    int     w_capacity{};
    std::cin    >>  w_capacity;
 
    std::cout   <<  "Items total: ";
    int     n{};
    std::cin    >>  n;
 
    std::cout   <<  "\nEnter "
                <<  n
                <<  " weights and costs of things:"
                <<  std::endl;
 
    T_weights_and_costs  weights_and_costs(n);
 
    for(int  i = 0; i < n; ++i)
    {
        std::cout   <<  "\n#"
                    <<  i + 1
                    <<  "\tweight\t: ";
 
        std::cin    >>  weights_and_costs[i].first;
 
        std::cout   <<  "\tcost\t: ";
        std::cin    >>  weights_and_costs[i].second;
    }//for
 
    std::sort
        (
            weights_and_costs.begin     (),
            weights_and_costs.end       ()
        );
 
    print_most_costly_contents_of_knapsack
        (
            w_capacity,
            weights_and_costs
        );
}
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
23.02.2016, 12:34
Привет! Вот еще темы с решениями:

Сколько у Пети способов попасть в школу, пройдя ровно K шагов. Пояснение по коду
Есть такая задача: На расстоянии N шагов от школы стоит Петя. Каждую минуту он...

Задача о рюкзаке 0-1
Дарова. Я снова с вопросом по динамическому программированию. Но т.к я...

Задача о Рюкзаке
Очень прошу с помощью. Нужен код на с++, решение задачи о рюкзаке методами :...

Задача о рюкзаке
И так я все сделал как вы и просили. Условие задачи о рюкзаке: Итак, пусть...


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

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

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