Я занимаюсь математикой, и мне нужно выполнить следующие задачи:
Учитывая неопределенный набор векторов, определите, какие из них могут суммироваться в единичный вектор (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
Я должен быть в состоянии запрограммировать компьютер для выполнения одной из вышеуказанных задач для дальнейшего исследования.
Для первого задания это вариант проблема подмножества сумм, которая может быть решена путем динамического программирования. Разница между проблемой суммы подмножеств и вашей проблемой заключается в том, что проблема суммы подмножеств имеет только одно измерение. В вашем случае вам необходимо расширить подход динамического программирования для работы с несколькими измерениями.
Для вашей второй задачи она идентична проблеме подмножества сумм.
Да, исследования …
Как насчет того, чтобы начать с грубой силы: создайте все 2 ^ N подмножеств вашего набора, и для каждого такого кандидата составьте сумму, если она соответствует цели, сохраните ее.