Test: Implement https://or.stackexchange.com/a/5876/5102

OptimalBackups.R

# https://or.stackexchange.com/a/5876/5102

library(tidyverse)

# Maximum number of snapshots to consider.
# TODO: reasonable upper bound? Probably: chose n large enough such that the resulting maximum number of snapshots that can be stored is < n.
n <- 100

# maximum capacity
C <- 2000

# s(t): new data added between t-1 and t (here: assumed to be constant)
# s(0): size of initial data
s <- function(t) {
  if (t == 0) {
    return(200)
  }
  return(25)
}

# partial sums: size until j
p <- function(j) {
  sapply(X = 0:j, FUN = s) %>% sum() %>% return()
}

# For 0 ≤ k ≤ t ≤ n let m[k][t] denote the minimum amount of storage required to store the first k + 1 snapshots,
# knowing that the last full backup happened at snapshot t.

# Caution: R uses 1 based indexing; answer uses 0  based index!

m <- matrix(NA, nrow = n+1, ncol = n+1)

m[1,1] <- s(0)

for (i in 1:(n-1)) {
  # print(min(m[i, (0:(i-1))+1], na.rm = TRUE) + p(i))
  m[i+1, i+1] <- min(m[i, (0:(i-1))+1], na.rm = TRUE) + p(i)
}

for (i in 1:(n-1)) {
  for (t in 0:(i-1)) {
    # print(m[i, t+1] + p(i) - p(t))
    m[i+1, t+1] <- m[i, t+1] + p(i) - p(t)
  }
}

mPrime <- vector(mode = "numeric", length = nrow(m))

for (i in 1:nrow(m)) {
  mPrime[i] <- min(m[i, 1:i])
}

which(mPrime < C) %>% max %>% print