Сумма, оканчивающаяся на 50

Question

Столкнулся с задачей (тема - динамическое программирование), условие которой звучит следующим образом:

В файле записана последовательность натуральных чисел. Гарантируется, что все числа различны. Рассматриваются всевозможные группы (произвольные подмножества) чисел, состоящие из любого количества элементов последовательности. Необходимо найти наибольшую сумму такой группы, заканчивающуюся на 50. Программа должна вывести эту сумму.

Ввод:

Вывод:

Я пытался создать такой массив, что в i-ой ячейке хранилось максимальное число, у которого остаток от деления на 100 равен i, а затем складывать значения симметрично относительно центра (например, 21-й элемент с 29-м), но это работает разве что если во входной последовательности уже есть числа, дающие в сумме 50 или 100.

Здесь, например, ничего не выйдет:

Ввод:

Вывод:

Мой код, который работает неверно:

int main()
{
    ifstream input("input.txt");
    ofstream output("output.txt");

    int quantity;
    input >> quantity;

    vector<int> arr(100);

    for (int i = 0; i < quantity; i++)
    {
        int number;
        input >> number;

        if (number > arr[number % 100])
        arr[number % 100] = number;
    }

    int sum = 0;

    for (int i = 0; i < 50; i++)
    {
        if (arr[i] != 0 && arr[50 - i] != 0)
        {
            sum += arr[i] + arr[50 - i];
            arr[i] = 0;
            arr[50 - i] = 0;
        }

        if (arr[i] != 0 && arr[100 - i] != 0)
        {
            sum += arr[i] + arr[100 - i];
            arr[i] = 0;
            arr[100 - i] = 0;
        }
    }

    output << sum << endl;
}

Какой существует оптимальный способ решить эту задачу?

Answer 1

Заводите таблицу размером n+1 строк и 100 столбцов.

Для i-го числа a[i]:   
  копируете i-строку в следующую  
  для каждой ячейки i-й строки:
     находите её сумму с a[i] (пусть t)
     и обновляете максимум в ячейке [t%100] следующей строки

В конце смотрите в 50-ю ячейку последней строки.

Можно также использовать мап, чтобы не иметь дела с пустыми ячейками.

P.S. Строк в принципе достаточно всего две, переключаясь между ними по чётности i

P.P.S. Можно использовать вообще одну строку, если ещё иметь пометки - было ли использовано текущее число для создания определённой суммы.

Answer 2

Ваш код работает неверно по многим причинам. Одна из них: вы не запоминаете все введёные числа. Если чисел два: 50 и 150, вы не построите их сумму. Этого достаточно, чтобы искать другое решение.

Математика

Для набора чисел a_j, 1 <= j <= n, определим функцию f(i, r) - максимальная сумма подмножества чисел a_j, 1 <= j <= i, которая сравнима с r mod 100.

f(n, 50) решает нашу задачу. Функция f определена для не для всех пар i, r. Суммы с нужным остатком может просто не быть. В этом случае доопределим f: f(i, r) = -inf, если требуемой суммы не существует. Например: f(0, 0) = 0 - это очевидно, f(0, r != 0) = -inf.

Функция f отвечает уравнению f(i, r) = max(f(i - 1, r), a_i + f(i - 1, (r - a_i) mod 100). Объяснение такое: для максимальной суммы для i могут быть два случая:

максимальная сумма включает a_i, тогда f(i, r) = a_i + f(i - 1, (r - a_i) mod 100);
максимальная сумма не включает a_i, тогда f(i, r) = f(i - 1, r).

Заранее мы не знаем какой случай имеет место, берем максимум от обоих вариантов. Уравнение правильно обрабатывает, случаи когда f = -inf.

Программирование

Если у нас есть набор значений f(i - 1, 0 <= r < 100), то по нему можно вычислить набор значений f(i, 0 <= r < 100). Так шаг за шагом мы построим f(0, *), f(1, *), ..., f(n, *).

Вместо реальной -inf в коде используется минимальное значение типа int. Это не полноценная замена, но работает если сумма не переполняет int. Если программа выдаст отрицательное число, нужной суммы не существует.

В C и C++ неудобно вычислять a mod b если a отрицательное число. Отрицательные числа могут возникать в выражении (r - a_i) mod 100. Везде заменим r на r + a_i: f(i, (r + a_i) mod 100) = max(f(i - 1, (r + a_i) mod 100), a_i + f(i - 1, r). Идея взята из ответа MBo.

// g++ -std=c++11 -pedantic -Wall -Wextra -Werror ending_fifty.cpp
 
#include <algorithm>
#include <array>
#include <cstdlib>
#include <iostream>
#include <limits>

int read_cardinal() {
    int n;
    if (!(std::cin >> n) || n < 0) {
        std::cerr << "Error\n";
        std::exit(1);
    }
    return n;
}

int main() {
    const int m = 100;
    std::array<int, m> f;
    f.fill(std::numeric_limits<int>::min());
    f[0] = 0;
    const int n = read_cardinal();
    for (int i = 0; i < n; ++i) {
        const int a = read_cardinal();
        auto fp = f;
        for (int r = 0; r < m; ++r) {
            const int s = (r + a) % m;
            f[s] = std::max(fp[s], a + fp[r]);
        }
    }
    std::cout << f[50] << '\n';
}

$g++ -std=c++11 -pedantic -Wall -Wextra -Werror ending_fifty.cpp
$ echo -e "6\n21\n29\n12\n72\n14\n28" | ./a.out
150
$ echo -e "3\n13\n14\n23" | ./a.out 
50
$ echo -e "3\n7\n14\n21" | ./a.out 
-2147483606

БЛОГ НА HUSL

Сумма, оканчивающаяся на 50

Ответы (2 шт):