Алгоритм выполнения следующей задачи?

Подскажите, пожалуйста, идеи по реализации следующей программы на C/C++:
1. Пользователь вводит число N
2. Пользователь вводит N цифр
3. Пользователь вводит результат

программа должна расставить знаки + и - между символами, чтобы получился результат.
Если решений не найдено, выводит "Нет решений"
  • Вопрос задан
  • 195 просмотров
Решения вопроса 1
longclaps
@longclaps
Надеюсь, все числа положительные )
#include <iostream>

using namespace std;

int main(int argc, const char *argv[]) {
    int n, capacity = 0, bufsize, target;
    cin >> n;
    int *terms = new int[n];
    for (int i = 0; i < n; i++) cin >> terms[i];
    cin >> target;
    for (int i = 1; i < n; i++) capacity += terms[i];
    bufsize = capacity * 2 + 1;
    target += capacity - terms[0];
    if (0 <= target && target < bufsize) {
        char **dp = new char *[n], *cur = new char[bufsize], *nxt;
        fill_n(cur, bufsize, 0);
        cur[capacity] = '+';
        for (int idx = 1; idx < n; idx++) {
            dp[idx] = nxt = new char[bufsize];
            fill_n(nxt, bufsize, 0);
            int t = terms[idx];
            for (int i = t; i < bufsize; i++) {
                if (cur[i]) nxt[i - t] = '-';
                if (cur[i - t]) nxt[i] = '+';
            }
            cur = nxt;
        }
        if (cur[target]) {
            char c, *ops = new char[n];
            for (int idx = n - 1; idx > 0; idx--) {
                ops[idx] = c = dp[idx][target];
                target -= c == '+' ? terms[idx] : -terms[idx];
            }
            cout << terms[0];
            for (int idx = 1; idx < n; idx++)
                cout << ops[idx] << terms[idx];
            return 0;
        }
    }
    cout << "Нет решений";
    return 0;
}
Ответ написан
Комментировать
Пригласить эксперта
Ответы на вопрос 2
tsarevfs
@tsarevfs Куратор тега C++
C++ developer
Если нужны идеи, то это частный случай задачи о рюкзаке или задачи о сумме подмножеств.
Ответ написан
Комментировать
Griboks
@Griboks
Самый простой алгоритм - перебрать все возможные варианты.
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы