Introduction

How dynamic programming (a knapsack variant) finds the optimum without enumerating everything, whereas expand.grid() can make memory explode?

Suppose you have \(100\) dollars and you need to allocate all of them across four monthly buckets: Transit, Mobile Data, Groceries Staples, and Gym. Each bucket can take \({0, 25, 50, 75, 100}\). How will you allocate your budget? What is your first move?

A natural idea is to use expand.grid() to list every combination, then keep only the plans where \(Transit + Mobile + Groceries + Gym = 100\).

Perfectly reasonable. After the sum-to-100 filter, you’re left with just 35 valid plans out of \((5^4 = 625\) tuples). It works, you feel clever, coffee tastes great!

Now it is getting real, it’s \(10\) categories, with possible allocations from \(0\) to \(100\) by \(5\%\) increments (so \(21\) choices each). Same instinct, right?

Use expand.grid(), filter to total \(= 100\), then compute the scores. Except this time is that the
number of the combinations is a little bit more:

\[\binom{29}{9} = 10{,}015{,}005\]

that’s ten million rows to build, store, filter and score.

Go one notch finer \(0..100\) by \(1\%\) then the number of the combinations is:

\[\binom{109}{9} \approx 4.26 \text{ trillion}\]

That’s not a data frame; that’s a black hole. R does what it can, then throws the white flag:

Error: cannot allocate vector of size …

Nothing’s wrong with your machine this is enumeration. expand.grid() is faithfully building what you asked for. The memory blow-up isn’t a bug; it’s the bill for the Cartesian menu you just ordered.

Why dynamic programming instead?

Rather than listing every full plan, knapsack DP keeps a compact table of partial bests:

What’s the best total utility we can get using the first \(i\) buckets with \(w\) dollars of budget available?

We’ll use a multiple-choice knapsack (exactly one choice per bucket) and show how DP recovers the exhaustive-search optimum without building massive Cartesian product.

Spend ($) Transit Mobile Data Groceries Gym
0 0 0 0 0
25 10 60 65 65
50 120 95 99 65
75 140 115 121 75
100 150 130 140 80

From the table, we see that most buckets exhibit diminishing returns: the early \(25\) dollars increments deliver more utility than later ones. For example, Gym has an “access jump” at \(25\) (it unlocks), followed by smaller gains. Transit, meanwhile, shows a threshold at \(50\) with a large jump.

These shapes tempt enumeration-but they’re exactly where dynamic programming shines.

The dynamic programming table (all at once)

What does this DP table tell us?

i \ w 0 25 50 75 100
0 (none) 0 0 0 0 0
1 (Transit) 0 10 120 140 150
2 (+ Mobile) 0 60 120 180 215
3 (+ Groc.) 0 65 125 185 245
4 (+ Gym) 0 65 130 190 250

This table \(dp[i, w]\) summarizes the best total utility achievable when you are allowed to use only the first \(i\) buckets and you have at most \(w\) dollars of budget left.

Formally: \[ dp[i, w] \;=\; \max\bigl\{\text{utility from buckets }1..i \text{ with spend} \le w\bigr\}. \]

Because in this example the entire budget must be used, the final answer sits at the last column with full budget, i.e. \(dp[i,100]\) where \(W = 100\).

More concretely, each cell is filled by considering how much to give the current bucket \(i\) and combining it with the best known result for the previous \(i-1\) buckets on the remaining budget:

\[ dp[i,w] \;=\; \max_{\substack{x \in \{0,25,50,75,100\}\\ x \le w}} \left\{\, dp[i-1,\,w-x] \;+\; v_i(x) \,\right\}. \]

We’ll now rebuild this table row by row to see exactly how each entry arises.

Row 0 - Base case (no buckets)

We can’t get any value without buckets:

i \ w 0 25 50 75 100
0 (none) 0 0 0 0 0

Example: \(dp[0,75]=0\). With no buckets allowed, you can not earn any utility no matter how much budget is available.

Row 1 - Add Transit

Think: If I can only spend on Transit, what’s the best I can do up to \(w\). i.e. with only Transit available, each cell is the best Transit utility that fits within \(w\)

  • \(w = 0:\ 0\) (do nothing)
  • \(w = 25:\ 10\)
  • \(w = 50:\ 120\)
  • \(w = 75:\ 140\)
  • \(w = 100:\ 150\)
i \ w 0 25 50 75 100
0 (none) 0 0 0 0 0
1 (Transit) 0 10 120 140 150

Row 2 - Add Mobile Data

Now add Mobile on top of Transit. At each budget \(w\), try Mobile at \(\{0,25,50,75,100\}\) (staying within \(w\)) and combine it with the best Transit plan for the remainder budget. Pick the largest total.

So Mobile \(= x\) and add row \(1\) on the remainder: \[ \mathrm{dp}[2,w] \;=\; \max_{0 \le x \le w} \Big\{ \mathrm{dp}[1,\,w - x] + \mathrm{Mobile}(x) \Big\}. \]

Compute all columns:

  • \(w = 0: x \in(0) \to 0\)
  • \(w = 25: x \in(0,25) \to \max(10, 60) = \mathbf{60}\)
  • \(w = 50: x \in(0,25, 50) \to \max(120, 70, 95)=\mathbf{120}\)
  • \(w = 75: x \in(0,25, 50, 75) \to \max(140, 180, 105, 115)=\mathbf{180}\)
  • \(w = 100: x \in(0,25, 50, 75, 100) \to \max(150, 200, 215, 125, 130) = \mathbf{215}\)
i \ w 0 25 50 75 100
0 (none) 0 0 0 0 0
1 (Transit) 0 10 120 140 150
2 (+ Mobile) 0 60 120 180 215

Row 3 - Add Groceries

Same idea: try a Groceries spend and combine with the best result from row 2 for the remainder.

So Groceries \(= x\) and add row \(2\) on the remainder: \[ \mathrm{dp}[3,w] \;=\; \max_{0 \le x \le w} \Big\{ \mathrm{dp}[2,\,w - x] + \mathrm{Groceries}(x) \Big\}. \]

  • \(w = 0: x \in(0) \to 0\)
  • \(w = 25: x \in(0,25) \to max(60, 65) = \mathbf{65}\)
  • \(w = 50: x \in(0,25, 50) \to max(120, 125, 99) = \mathbf{125}\)
  • \(w = 75: x \in(0,25, 50, 75) \to max(180, 185, 159, 121) = \mathbf{185}\)
  • \(w = 100: x \in(0,25, 50, 75, 100) \to max(215, 245, 219, 181, 140) = \mathbf{245}\)
i \ w 0 25 50 75 100
0 (none) 0 0 0 0 0
1 (Transit) 0 10 120 140 150
2 (+ Mobile) 0 60 120 180 215
3 (+ Groc.) 0 65 125 185 245

Row 4 - Add Gym

Again, try Gym at each allowed spend and combine with the best from row 3 for the leftover budget.

\[ \mathrm{dp}[4,w] \;=\; \max_{0 \le x \le w} \Big\{ \mathrm{dp}[3,\,w - x] + \mathrm{Gym}(x) \Big\}. \]

  • \(w = 0: x \in(0) \to 0\)
  • \(w = 25: x \in(0,25) \to max(65, 40) = \mathbf{65}\)
  • \(w = 50: x \in(0,25, 50) \to max(125, 130, 65) = \mathbf{130}\)
  • \(w = 75: x \in(0,25, 50, 75) \to max(185, 190, 130, 75) = \mathbf{190}\)
  • \(w = 100: x \in(0,25, 50, 75, 100) \to max(245, 250, 190, 140, 80) = \mathbf{250}\)
i \ w 0 25 50 75 100
0 (none) 0 0 0 0 0
1 (Transit) 0 10 120 140 150
2 (+ Mobile) 0 60 120 180 215
3 (+ Groc.) 0 65 125 185 245
4 (+ Gym) 0 65 130 190 250

Bottom-right cell:
Best total utility with all four buckets and \(W=100\) is \({dp[4,100] = 250}\).

Final answer & how to read it back

Where is the final value? Look at the last row and full budget: \(dp[n,W]\), here \(dp[4,100]=250\).

How do we recover the actual allocation? At each cell \((i,w)\), the DP chose the spend \(x\) for bucket \(i\) that made \(dp[i-1, w-x] + v_i(x)\) as large as possible. To read it back manually:

  1. Start at \((i,w)=(i,100)\) where the maximum is.
  2. Find the Gym spend \(x\) that explains the cell: \(dp[3, 100-x] + \text{Gym}(x) = 250\). Only \(x=25\) works (\(185 + 65 = 250\)). So Gym = \(25\), now \(w=75\).
  3. Move to \((3,75)\) and do the same for Groceries: \(dp[2, 75-x] + \text{Groc}(x) = 185\). Only \(x=25\) works (\(120 + 65 = 185\)). So Groceries = \(25\), now \(w=50\).
  4. Move to \((2,50)\) for Mobile: \(dp[1, 50-x] + \text{Mobile}(x) = 120\). Here \(x=0\) works. So Mobile = \(0\), still \(w=50\).
  5. Move to \((1,50)\) for Transit: \(dp[0, 50-x] + \text{Transit}(x) = 120\). Here \(x=50\) works. So Transit = \(50\), now \(w=0\) and we are done.

\[ dp[i,w] \;=\; \max_{\substack{x \in \{0,25,50,75,100\}\\ x \le w}} \left\{\, dp[i-1,\,w-x] \;+\; v_i(x) \,\right\}. \]

To recover the allocation, start at \((i,w)=(n,W)\) and repeatedly choose \[ x_i \;\in\; \arg\max_{x \le w} \left\{\, dp[i-1,\,w-x] \;+\; v_i(x) \,\right\}, \] then update \(w \leftarrow w - x_i\) and \(i \leftarrow i-1\) until \(i=0\).

Best solution (allocation):

Total utility = 250 (budget used: $100).

Knapsack DP and expand.grid in R

# Use whole dollars (1$ increments from 0$ to 100$ total)
amounts <- 0:100
groups <- c("Transit", "Mobile", "Groceries", "Gym")

# Random, non-linear, monotone-ish utility curve for each group
# (sqrt + log + sublinear power + optional threshold bonus + noise, then cummax)
rand_util <- function(x) {
  a <- runif(1, 30, 60)
  b <- runif(1, 10, 25)
  p <- runif(1, 0.25, 0.55) # sublinear power -> diminishing-ish
  thr <- sample(20:60, 1) # threshold unlock point
  bonus <- ifelse(x >= thr, runif(1, 10, 40), 0)
  u <- a * sqrt(x) + b * log1p(x) + 5 * (x^p) + bonus + rnorm(length(x), sd = 0.4)
  u <- cummax(u) # enforce non-decreasing
  u <- u - u[1] # start at 0
  as.numeric(round(u, 3))
}

# Build utility lookups (vectors of length 101; index = amount + 1)
set.seed(42369) # for reproducibility
util <- setNames(lapply(groups, \(.) rand_util(amounts)), groups)

# Plot utility curves with base R (2x2 grid)
op <- par(mfrow = c(2, 2), mar = c(4, 4, 2, 1))
for (g in groups) {
  plot(amounts, util[[g]],
    col = gray(.5),
    lwd = 3,
    type = "l",
    xlab = "Spend ($)",
    ylab = "Utility",
    main = paste("Utility:", g)
  )
}

# This constructs the full 4-way grid over 0..100 by 1, then filters to exact sum = 100.
# NOTE: 101^4 = 104,060,401 rows before filtering. Depending on your machine, it may take time and
# memory to complete.

start_eg <- Sys.time() # starting time
eg <- expand.grid(
  Transit = amounts,
  Mobile = amounts,
  Groceries = amounts,
  Gym = amounts,
  KEEP.OUT.ATTRS = FALSE,
  stringsAsFactors = FALSE
)

# Keep only allocations that sum exactly to 100
eg <- eg[rowSums(eg) == 100, , drop = FALSE]

# Score each plan using the utility lookups (index = dollars + 1)
score <- util$Transit[eg$Transit + 1] +
  util$Mobile[eg$Mobile + 1] +
  util$Groceries[eg$Groceries + 1] +
  util$Gym[eg$Gym + 1]

best_idx_eg <- which.max(score)
best_value_eg <- score[best_idx_eg]
alloc_eg <- eg[best_idx_eg, , drop = FALSE]
end_eg <- Sys.time() # ending time
time_eg <- end_eg - start_eg
exact_sum_dp <- function(W, 
                         groups, 
                         util) {
  start_dp <- Sys.time() # starting time
  n <- length(groups)
  # dp[i+1, w+1] = best value using first i groups to spend EXACTLY w
  dp <- matrix(-Inf, nrow = n + 1L, ncol = W + 1L)
  back <- matrix(NA_integer_, nrow = n + 1L, ncol = W + 1L)
  dp[1, 1] <- 0 # 0 groups and spend 0 => 0 value
  t_dp <- for (i in 1:n) {
    u <- util[[i]] # length 101, index by amount+1
    for (w in 0:W) {
      best <- -Inf
      bestx <- 0L
      for (x in 0:w) {
        prev <- dp[i, (w - x) + 1L]
        if (!is.infinite(prev)) {
          val <- prev + u[x + 1L]
          if (val > best) {
            best <- val
            bestx <- x
          }
        }
      }
      dp[i + 1L, w + 1L] <- best
      back[i + 1L, w + 1L] <- bestx
    }
  }
  best_value_dp <- dp[n + 1L, W + 1L]

  # Traceback allocation
  alloc_dp <- integer(n)
  w <- W
  for (i in n:1) {
    x <- back[i + 1L, w + 1L]
    alloc_dp[i] <- x
    w <- w - x
  }
  names(alloc_dp) <- groups
  end_dp <- Sys.time() # ending time
  time_dp <- end_dp - start_dp
  list(
    best_value_dp = best_value_dp,
    alloc_dp = alloc_dp,
    dp = dp,
    back = back,
    t_dp = t_dp,
    time_dp = time_dp
  )
}

# execute
res_dp <- exact_sum_dp(W = 100L, groups, util)
best_value_dp <- res_dp$best_value_dp
alloc_dp <- res_dp$alloc_dp
time_dp <- res_dp$time_dp

Knapsack DP vs. expand.grid in R

Best Value, Runtime & Allocation by Method
Method BestValue Seconds Transit Mobile Groceries Gym
Expand grid 1196.907 5.3360 37 24 14 25
DP (Knapsack) 1196.907 0.0053 37 24 14 25

Repository

References

  1. Kleinberg, J., & Tardos, É. (2022). Algorithm Design (2nd ed.). Pearson. (DP & knapsack textbook treatment)
  2. Algorithm Visualizer. Knapsack Problem - Dynamic Programming (JavaScript visualization). Available at: https://algorithm-visualizer.org/dynamic-programming/knapsack-problem .