Есть ли алгоритмический способ решения любой из этих двух задач в программировании?

Я занимаюсь математикой, и мне нужно выполнить следующие задачи:

Учитывая неопределенный набор векторов, определите, какие из них могут суммироваться в единичный вектор (1, 1, …, 1)

Например, рассмотрим векторы

x1 = (1 0 0)
x2 = (0 1 1)
x3 = (1 0 0)

Если вы сложите векторы x1 и x2 вместе, вы получите (1, 1, 1),

Или для большего примера

x1 = (1 0 0 0)
x2 = (0 1 1 0)
x3 = (0 0 1 1)
x4 = (0 0 0 1)

Если вы сложите векторы 1, 2 и 4 вместе, вы получите (1, 1, 1, 1),

Мне нужен алгоритм, который может сделать это в целом.

Второе задание … учитывая неопределенный набор чисел, определите, какие из них равны 1.

Например:

x1 = 0.2
x2 = 0.5
x3 = 0.6
x4 = 0.4
x5 = 0.3
x6 = 0.1
x1 + x2 + x5 = 0.2 + 0.5 + 0.3 = 1

Но также, x1 + x4 + x5 + x6 = 1

Я должен быть в состоянии запрограммировать компьютер для выполнения одной из вышеуказанных задач для дальнейшего исследования.

-6

Решение

Для первого задания это вариант проблема подмножества сумм, которая может быть решена путем динамического программирования. Разница между проблемой суммы подмножеств и вашей проблемой заключается в том, что проблема суммы подмножеств имеет только одно измерение. В вашем случае вам необходимо расширить подход динамического программирования для работы с несколькими измерениями.

Для вашей второй задачи она идентична проблеме подмножества сумм.

2

Другие решения

Да, исследования …

Как насчет того, чтобы начать с грубой силы: создайте все 2 ^ N подмножеств вашего набора, и для каждого такого кандидата составьте сумму, если она соответствует цели, сохраните ее.

0