Это идеальная проблема для решения с использованием динамического программирования, и повторение, описанное @lijie, является совершенно правильным подходом, с несколькими незначительными изменениями, чтобы обеспечить рассмотрение всех возможностей. Есть два ключевых наблюдения: (a) любая последовательность операций объединения приводит к набору непересекающихся суммированных подпоследовательностей исходного вектора, и (b) для оптимальной последовательности соединения, если мы посмотрим на Право любой суммированной подпоследовательности (m ... n), эта часть является оптимальным решением проблемы: "найти оптимальную последовательность соединения для субвектора (n + 1) ... N, такую, что получающийся в результате финал последовательность отсортирована, и все элементы> = sum (m ... n).
Реализация непосредственного повторения, конечно, привела бы к алгоритму экспоненциального времени, но простая настройка с использованием динамического программирования делает его O (N ^ 2), потому что, по существу, все (m, n) пары рассматриваются один раз. Простой способ реализовать рекуррентность с использованием динамического программирования - это иметь структуру данных, индексированную (m, n), которая хранит результаты f (m, n) после их вычисления, чтобы в следующий раз мы вызывали f (m) , п), мы можем посмотреть ранее сохраненные результаты. Следующий код делает это с использованием языка программирования R. Я использую формулировку, в которой мы хотим найти минимальное число объединений, чтобы получить неубывающую последовательность. Для новичков в R, чтобы протестировать этот код, просто скачайте R из любого зеркала (Google «R Project») запустите его и вставьте в консоль два определения функций (f и solve), а затем решите любой вектор, используя «solve (c (...))», как в примеры ниже.
f <- function(m,n) {
name <- paste(m,n)
nCalls <<- nCalls + 1
# use <<- for global assignment
if( !is.null( Saved[[ name ]] ) ) {
# the solution for (m,n) has been cached, look it up
nCached <<- nCached + 1
return( Saved[[ name ]] )
}
N <- length(vec) # vec is global to this function
sum.mn <- -Inf
if(m >= 1)
sum.mn <- sum( vec[m:n] )
if(n == N) { # boundary case: the (m,n) range includes the last number
result <- list( num = 0, joins = list(), seq = c())
} else
{
bestNum <- Inf
bestJoins <- list()
bestSeq <- c()
for( k in (n+1):N ) {
sum.nk <- sum( vec[ (n+1):k ] )
if( sum.nk < sum.mn ) next
joinRest <- f( n+1, k )
numJoins <- joinRest$num + k-n-1
if( numJoins < bestNum ) {
bestNum <- numJoins
if( k == n+1 )
bestJoins <- joinRest$joins else
bestJoins <- c( list(c(n+1,k)), joinRest$joins )
bestSeq <- c( sum.nk, joinRest$seq)
}
}
result <- list( num = bestNum, joins = bestJoins, seq = bestSeq )
}
Saved[[ name ]] <<- result
result
}
solve <- function(input) {
vec <<- input
nCalls <<- 0
nCached <<- 0
Saved <<- c()
result <- f(0,0)
cat( 'Num calls to f = ', nCalls, ', Cached = ', nCached, '\n')
cat( 'Min joins = ', result$num, '\n')
cat( 'Opt summed subsequences: ')
cat( do.call( paste,
lapply(result$joins,
function(pair) paste(pair[1], pair[2], sep=':' ))),
'\n')
cat( 'Final Sequence: ', result$seq, '\n' )
}
Вот несколько примеров прогонов:
> solve(c(2,8,2,2,9,12))
Num calls to f = 22 , Cached = 4
Min joins = 2
Opt summed subsequences: 2:3 4:5
Final Sequence: 2 10 11 12
> solve(c(1,1,1,1,1))
Num calls to f = 19 , Cached = 3
Min joins = 0
Opt summed subsequences:
Final Sequence: 1 1 1 1 1
> solve(c(4,3,10,11))
Num calls to f = 10 , Cached = 0
Min joins = 1
Opt summed subsequences: 1:2
Final Sequence: 7 10 11
> solve(c (2, 8, 2, 2, 8, 3, 8, 9, 9, 2, 9, 8, 8, 7, 4, 2, 7, 5, 9, 4, 6, 7, 4, 7, 3, 4, 7, 9, 1, 2, 5, 1, 8, 7, 3, 3, 6, 3, 8, 5, 6, 5))
Num calls to f = 3982 , Cached = 3225
Min joins = 30
Opt summed subsequences: 2:3 4:5 6:7 8:9 10:12 13:16 17:19 20:23 24:27 28:33 34:42
Final Sequence: 2 10 10 11 18 19 21 21 21 21 26 46
Обратите внимание, что минимальное число объединений для последовательности, рассматриваемой @kotlinski, составляет 30, а не 32 или 33.