Вопрос Просьба помочь с задачкой по программированию, алгоритм или код

[данил5555]

Здравствуйте, помогите решить задачу.

Есть n троек чисел ti, ci, di (i-индекс). Из них нужно выбрать ровно m троек так, чтобы значение выражения |сумма выбранных t| + |сумма выбранных с| + |сумма выбранных d| была максимально возможной.

Входные данные. ( 1 ≤ n ≤ 1000 , 0 ≤ m ≤ n ) и (− 10^10 ≤ ti , di ,ci ≤ 10^10)

Пробовал тупо перебором, но на каком-то тесте программа выдает неправильный ответ

#include <iostream>

#include <vector>

#include <cmath>

#include <stdio.h>



using namespace std;



int main() {

int n, m; cin >> n >> m;

vector<long long> t,d,c;

long long max = 0;

long long sumT = 0, sumD = 0, sumC = 0, cur = 0;

for (int i = 0; i < n; ++i) cin >> t >> d >> c;

for (int i = 0; i < (1 << n); ++i) {

if (__builtin_popcount(i) == m) {

sumT = 0; sumD = 0; sumC = 0; cur = 0;

for (int j = 0; j < n; ++j) {

if (i & (1 << j)) {

sumT += t[j];

sumD += d[j];

sumC += c[j];

}

}

cur = abs(sumT) + abs(sumD) + abs(sumC);



if (cur > max) {

max = cur;

}

}

}

cout << max << endl;

return 0;

}

 

[SoFTeR]

Ваш код решает задачу перебором всех возможных комбинаций троек чисел. Однако, такой подход может быть неэффективным, если n достаточно велико. Ваш код работает за время O(2^n * n), что может быть слишком медленным для больших значений n.

Однако, есть другой способ решения этой задачи, который работает быстрее. Вы можете использовать динамическое программирование для решения этой задачи. Сложность такого алгоритма будет O(n * m), что значительно быстрее, чем ваш текущий подход.

Вот пример кода, который решает эту задачу с помощью динамического программирования: #include
#include
#include
#include

using namespace std;

int main() {
int n, m;
cin >> n >> m;
vector t, d, c;
for (int i = 0; i < n; ++i) cin >> t >> d >> c;

vector dp(m + 1, vector(n + 1, -1e18));
dp[0][0] = 0;
for (int i = 0; i < n; ++i) {
for (int j = 0; j

 

[--YURA--]

ааааа, до меня дошла что это за задача, ну удаче тебе с ней)

 

[yurka321]

Проверьте, как это работает, и работает ли вообще #include
#include
#include
#include
#include

using namespace std;

struct Triple {
long long a, b, c;
private:
friend istream& operator>>(istream& inp, Triple& t) {
return inp >> t.a >> t.b >> t.c;
}
};

unsigned long long max_sum(const vector box, const size_t m) {
auto sum_a = [](long long acc, const Triple t) { return acc += t.a; };
auto sum_b = [](long long acc, const Triple t) { return acc += t.b; };
auto sum_c = [](long long acc, const Triple t) { return acc += t.c; };
auto sum_l = abs(accumulate(box.begin(), box.begin() + m, 0LL, sum_a));
sum_l += abs(accumulate(box.begin(), box.begin() + m, 0LL, sum_b));
sum_l += abs(accumulate(box.begin(), box.begin() + m, 0LL, sum_c));
auto sum_r = abs(accumulate(box.rbegin(), box.rbegin() + m, 0LL, sum_a));
sum_r += abs(accumulate(box.rbegin(), box.rbegin() + m, 0LL, sum_b));
sum_r += abs(accumulate(box.rbegin(), box.rbegin() + m, 0LL, sum_c));
return max(sum_l, sum_r);
}

int main() {
size_t n, m;
cin >> n >> m;
vector box;
for (auto& x : box) cin >> x;
auto copm_a = [](const Triple& l, const Triple& r) { return l.a < r.a; };
auto copm_b = [](const Triple& l, const Triple& r) { return l.b < r.b; };
auto copm_c = [](const Triple& l, const Triple& r) { return l.c < r.c; };
sort(box.begin(), box.end(), copm_a);
auto sum_a = max_sum(box, m);
sort(box.begin(), box.end(), copm_b);
auto sum_b = max_sum(box, m);
sort(box.begin(), box.end(), copm_c);
auto sum_c = max_sum(box, m);
auto sum_m = max(max(sum_a, sum_b), sum_c);
cout

 

[•KFC•]

А ты в курсе, сколько будет 1