создать специальную матрицу (максимальное значение суммы столбцов минимально) с заданным номером столбца из вектора - PullRequest
Новая
       9

создать специальную матрицу (максимальное значение суммы столбцов минимально) с заданным номером столбца из вектора

0 голосов
/ 13 февраля 2019

Недавно я столкнулся с таким вопросом: для заданного вектора нужно создать специальную матрицу с заданным номером столбца.Следует отметить, что если элементов в векторе недостаточно для заполнения сгенерированной матрицы, то поместите 0 в последнюю строку сгенерированной матрицы.Для сгенерированной матрицы требуется, чтобы максимальное значение суммы столбцов было минимальным.

Ниже приведен код для данного вопроса: 

x <- c(10, 10, 9, 21, 8, 3, 7, 23, 1, 5, 26)
x
ncol <- 4

x <- sort(x, decreasing = TRUE)
x

nx <- length(x)
nrow <- ceiling(nx / ncol)

# add 0 in the end
if (nx < nrow * ncol) {
  x <- c(x, rep(0, length.out = nrow * ncol - nx))
}
x

Вот правильныйматрица, что я хочу! 

# generate mat_a
mat_a <- rbind(c(26, 23, 21, 10),
               c(5, 7, 8, 10),
               c(0, 1, 3, 9))
mat_a
# max value of column sum
max(colSums(mat_a)) # 32

Матрица ниже - это то, что я получил, но это неверно! 

# generate mat_b
mat_b <- rbind(c(26, 23, 21, 10),
               c(7, 8, 9, 10),
               c(0, 1, 3, 5))
mat_b
max(colSums(mat_b)) # 33

Поскольку max(colSums(mat_a)) < max(colSums(mat_b)), mat_a - искомая матрица.

Из приведенного выше кода мы знаем, что mat_a является искомой матрицей, поскольку max(colSums(mat_a)) < max(colSums(mat_b)).Я понимаю, что существует много матриц, которые могут быть сгенерированы из вектора, но матрица с вышеуказанным требованием является только одной (или немного, если генерируются одинаковые значения).Кажется, комбинаторные алгоритмы или проблемы динамического программирования, но, к сожалению, я не могу понять, как получить решение для вышеуказанного вопроса.Я ценю, что вы можете дать некоторые подсказки о проблеме или дать эффективные решения.

1 Ответ

0 голосов
/ 13 февраля 2019

Здесь возможен жадный эвристический подход, который, вероятно, работает только тогда, когда все значения в x неотрицательны.

Сначала начиная с самых больших значений.Инициализируйте первую строку с самыми большими значениями.Затем добавьте каждое последующее ненулевое значение в столбец с наименьшей суммой. 

x <- c(10, 10, 9, 21, 8, 3, 7, 23, 1, 5, 26)
x <- sort(x, decreasing=TRUE)
nc <- 4L
nr <- ceiling(length(x) / 4)

#Initialize the first row with the largest values
y <- c(x[seq_len(nc)], rep(0, nc*nr-4L))
#use list to store each row of the final matrix
yl <- split(y, (seq_along(y)-1L) %% nc)

#for subsequent values
for (k in (nc+1L):length(x)) {
    #find the smallest sum among the rows provided the rows are not totally filled
    idx <- names(which.min(lapply(yl[sapply(yl, function(x) any(x==0))], sum)))

    #store this value the appropriate row
    yl[[idx]][min(which(yl[[idx]]==0L))] <- x[k]
}

#output desired matrix
matrix(unlist(yl), ncol=nc)

output: 

     [,1] [,2] [,3] [,4]
[1,]   26   23   21   10
[2,]    5    7    8   10
[3,]    0    1    3    9
...