Skip to content

Commit cd8473a

Browse files
kamalovniyazkamalovniyaz
committed
add
1 parent a8fb461 commit cd8473a

File tree

8 files changed

+75
-17
lines changed

8 files changed

+75
-17
lines changed

‎README.md

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -5,9 +5,9 @@
55

66
## 1. Информация о студенте
77

8-
**Номер группы**: 00-000
8+
**Номер группы**: 11-104
99

10-
**Фамилия и Имя**: Иванов Иван
10+
**Фамилия и Имя**: Камалов Нияз
1111

1212
## 2. Описание задания
1313

‎src/bits.cpp

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -6,12 +6,12 @@ namespace assignment {
66

77
bool is_bit_set(int mask, int pos) {
88
assert(mask >= 0 && pos >= 0 && pos < 30);
9-
return false;
9+
return (mask & (1 << pos)) != 0;
1010
}
1111

1212
int set_bit(int mask, int pos) {
1313
assert(mask >= 0 && pos >= 0 && pos < 30);
14-
return 0;
14+
return mask | (1 << pos);
1515
}
1616

1717
std::vector<int> mask2indices(const std::vector<int>& elems, int mask) {

‎src/knapsack/backtracking.cpp

Lines changed: 8 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -35,13 +35,19 @@ namespace assignment {
3535

3636
// ... если текущая "польза" максимальна, обновляем наилучшую "пользу"
3737
if (profit > best_profit) {
38-
// ...
38+
best_profit = profit;
39+
best_profit_mask = mask;
3940
}
4041

4142
// рассматриваем следующий элемент
4243
index += 1;
44+
if (index == static_cast<int>(profits.size())) {
45+
return;
46+
}
4347

4448
// ... рекурсивные вызовы со включением/исключением следующего элемента
49+
solve(profits, weights, capacity, index, mask, weight, profit, best_profit, best_profit_mask);
50+
solve(profits, weights, capacity, index, set_bit(mask, index), weight + weights[index], profit + profits[index], best_profit, best_profit_mask);
4551
}
4652

47-
} // namespace assignment
53+
} // namespace assignment

‎src/knapsack/bit_masking.cpp

Lines changed: 8 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -33,6 +33,9 @@ namespace assignment {
3333
// вычисление общего веса рассматриваемых элементов
3434
const int curr_weight = sum_helper(masked_weights);
3535

36+
if (curr_weight > capacity) {
37+
continue;
38+
}
3639
// ... обработка случая превышения емкости рюкзака
3740

3841
// массив из "пользы" рассматриваемых элементов
@@ -41,12 +44,15 @@ namespace assignment {
4144
// вычисление общей "пользы" рассматриваемых элементов
4245
const int curr_profit = sum_helper(masked_profits);
4346

47+
if (curr_profit > best_profit) {
48+
best_profit = curr_profit;
49+
best_profit_mask = mask;
50+
}
4451
// ... обработка случая нахождения большего значения "пользы"
4552
}
4653

4754
// ... возвращение итогового результата: используйте mask2indices;
48-
49-
return {};
55+
return mask2indices(profits, best_profit_mask);
5056
}
5157

5258
} // namespace assignment

‎src/subset_sum/backtracking.cpp

Lines changed: 16 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -32,30 +32,44 @@ namespace assignment {
3232
}
3333

3434
// Ограничение 1: текущая сумма должна быть меньше целевой
35-
if (true /* ... */) {
35+
if (sum > target_sum) {
3636
// если превысили целевую сумму, то сделать ее меньше уже не получится (все элементы множества положительные)
3737
return;
3838
}
3939

4040
// Ограничение 2: "остаточная сумма" + "текущая сумма" должны быть больше или равны "целевой сумме"
41-
if (true /* ... */) {
41+
if (sum + residual < target_sum) {
4242
// сумму невозможно будет набрать с оставшимися элементами множества
4343
return;
4444
}
4545

4646
// если найдено подмножество с целевой суммой, то сохраняем в результат это подмножество
4747
if (sum == target_sum) {
48+
const auto num_elems = static_cast<int>(set.size()); // N
49+
auto subset = std::vector<int>();
50+
for (int j = 0; j < num_elems; j++) {
51+
if (is_bit_set(mask,j)) {
52+
subset.push_back(j);
53+
}
54+
}
55+
indices.push_back(subset);
4856
// ... сохранение в результат
4957
// ... нужно ли в этой ветке рекурсии рассматривать следующие элементы?
5058
}
5159

60+
if (index == static_cast<int>(set.size() - 1)) {
61+
return;
62+
}
63+
5264
// рассматриваем следующий элемент
5365
index += 1;
5466

5567
// обновляется несмотря на включение/исключение элемента => почему?
5668
residual -= set[index];
5769

5870
// рекурсивный вызов со включением/исключением элемента с текущим индексом ...
71+
search(set, index, mask, sum, residual, target_sum, indices);
72+
search(set, index, set_bit(mask, index), sum + set[index], residual, target_sum, indices);
5973
}
6074

6175
} // namespace assignment

‎src/subset_sum/bit_masking.cpp

Lines changed: 19 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -7,19 +7,35 @@
77
namespace assignment {
88

99
std::vector<std::vector<int>> SubsetSumBitMasking::search(const std::vector<int>& set, int target_sum) const {
10-
assert(target_sum > 0 && set.size() <= 16);
11-
12-
std::vector<std::vector<int>> indices;
10+
assert(set.size() <= 16);
1311

1412
const auto num_elems = static_cast<int>(set.size()); // N
1513
const int num_subsets = 1 << num_elems; // 2^N
1614

15+
// выделяем память
16+
auto indices = std::vector<std::vector<int>>();
17+
1718
// 1. Внешний цикл: пробегаемся по всем битовым маскам от 0..00 до 1..11
1819
// 2. Внутренний цикл: проверка разрядов битовой маски и генерация подмножества, ассоциирующегося с этой маской
1920
// 3. Подсчет суммы текущего подмножества, сохранение индексов подмножества с целевой суммой в результат
2021
// Tips: можно пропустить итерацию, если сумма текущего подмножества стала больше целевой суммы
22+
for (int i = 0; i < num_subsets; i++) {
23+
auto subset = std::vector<int>();
24+
int sum = 0;
25+
for (int j = 0; j < num_elems; j++) {
26+
if (is_bit_set(i,j)) {
27+
subset.push_back(j);
28+
sum += set[j];
29+
}
30+
}
31+
if (sum == target_sum) {
32+
indices.push_back(subset);
33+
}
34+
}
2135

2236
return indices;
37+
38+
2339
}
2440

2541
} // namespace assignment

‎src/subsets/backtracking.cpp

Lines changed: 10 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -26,15 +26,22 @@ namespace assignment {
2626
assert(mask >= 0 && index >= -1);
2727

2828
// Ограничение: рассмотрены все элементы множества
29+
const auto num_elems = static_cast<int>(set.size()); // N
2930
if (index == static_cast<int>(set.size()) - 1) {
30-
31-
// ... сохранение полученного подмножества
32-
31+
auto subset = std::vector<int>();
32+
for (int j = 0; j < num_elems; j++) {
33+
if (is_bit_set(mask,j)) {
34+
subset.push_back(j);
35+
}
36+
}
37+
subsets.push_back(subset);
3338
return; // возвращаемся по дереву рекурсии
3439
}
3540

3641
index += 1; // рассматриваем следующий элемент
3742

43+
generate(set, index, mask, subsets);
44+
generate(set, index, set_bit(mask, index), subsets);
3845
// здесь должны быть рекурсивные вызовы ...
3946
// включаем или не включаем элемент с текущим индексом в подмножество (используя битовую маску)
4047
}

‎src/subsets/bit_masking.cpp

Lines changed: 10 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -13,11 +13,20 @@ namespace assignment {
1313
const int num_subsets = 1 << num_elems; // 2^N
1414

1515
// выделяем память
16-
auto subsets = std::vector<std::vector<int>>(num_subsets);
16+
auto subsets = std::vector<std::vector<int>>();
1717

1818
// 1. Внешний цикл: пробегаемся по всем битовым маскам от 0..00 до 1..11
1919
// 2. Внутренний цикл: проверка разрядов битовой маски и генерация подмножества, ассоциирующегося с этой маской
2020
// Tips: для проверки разряда бита на 1 (единицу) используйте функцию is_bit_set
21+
for (int i = 0; i < num_subsets; i++) {
22+
auto subset = std::vector<int>();
23+
for (int j = 0; j < num_elems; j++) {
24+
if (is_bit_set(i,j)) {
25+
subset.push_back(j);
26+
}
27+
}
28+
subsets.push_back(subset);
29+
}
2130

2231
return subsets;
2332
}

0 commit comments

Comments
 (0)