Problema de la Mochila (Knapsack Problem)
Jonathan Cano Bedoya
2026-06-18
Introducción
Camila tiene una mochila con capacidad máxima de 50 kilogramos. Dispone de 10 productos, cada uno con un peso y un beneficio asociado (calorías y nutrientes).
El objetivo consiste en determinar qué combinación de productos maximiza el beneficio total sin exceder la capacidad de la mochila.
Información del problema
pesos <- c(10,20,30,5,7,12,25,15,18,6)
beneficios <- c(60,100,120,30,24,50,75,80,95,40)
capacidad <- 50Número de combinaciones posibles
Para un conjunto de 10 elementos, el número total de combinaciones no vacías es:
\[ 2^{10}-1=1023 \]
Generación de combinaciones
todas_combinaciones <- list()
for(k in 1:10){
combinaciones_k <- combn(1:10,
k,
simplify = FALSE)
todas_combinaciones <- c(todas_combinaciones,
combinaciones_k)
}
length(todas_combinaciones)## [1] 1023Construcción de la base de resultados
todos_resultados <- data.frame(
combinacion = character(),
peso_total = numeric(),
beneficio_total = numeric(),
n_items = integer(),
factible = logical(),
stringsAsFactors = FALSE
)Evaluación de todas las combinaciones
for(k in 1:10){
combinaciones <- combn(1:10,
k,
simplify = FALSE)
for(combo in combinaciones){
peso_combo <- sum(pesos[combo])
beneficio_combo <- sum(beneficios[combo])
todos_resultados <- rbind(
todos_resultados,
data.frame(
combinacion = paste(combo,
collapse = ","),
peso_total = peso_combo,
beneficio_total = beneficio_combo,
n_items = length(combo),
factible = peso_combo <= capacidad
)
)
}
}Exploración inicial
Primeras combinaciones
head(todos_resultados,20)## combinacion peso_total beneficio_total n_items factible
## 1 1 10 60 1 TRUE
## 2 2 20 100 1 TRUE
## 3 3 30 120 1 TRUE
## 4 4 5 30 1 TRUE
## 5 5 7 24 1 TRUE
## 6 6 12 50 1 TRUE
## 7 7 25 75 1 TRUE
## 8 8 15 80 1 TRUE
## 9 9 18 95 1 TRUE
## 10 10 6 40 1 TRUE
## 11 1,2 30 160 2 TRUE
## 12 1,3 40 180 2 TRUE
## 13 1,4 15 90 2 TRUE
## 14 1,5 17 84 2 TRUE
## 15 1,6 22 110 2 TRUE
## 16 1,7 35 135 2 TRUE
## 17 1,8 25 140 2 TRUE
## 18 1,9 28 155 2 TRUE
## 19 1,10 16 100 2 TRUE
## 20 2,3 50 220 2 TRUECombinación 259
todos_resultados[259,]## combinacion peso_total beneficio_total n_items factible
## 259 1,8,9,10 49 275 4 TRUECombinaciones factibles y no factibles
table(todos_resultados$factible)##
## FALSE TRUE
## 820 203Análisis por número de ítems
library(dplyr)##
## Adjuntando el paquete: 'dplyr'## The following objects are masked from 'package:stats':
##
## filter, lag## The following objects are masked from 'package:base':
##
## intersect, setdiff, setequal, unionresumen_por_n_items <- todos_resultados %>%
group_by(n_items) %>%
summarise(
min_peso = min(peso_total),
max_peso = max(peso_total),
min_beneficio = min(beneficio_total),
max_beneficio = max(beneficio_total),
n_factibles = sum(factible),
n_total = n()
)
resumen_por_n_items## # A tibble: 10 × 7
## n_items min_peso max_peso min_beneficio max_beneficio n_factibles n_total
## <int> <dbl> <dbl> <dbl> <dbl> <int> <int>
## 1 1 5 30 24 120 10 10
## 2 2 11 55 54 220 44 45
## 3 3 18 75 94 315 83 120
## 4 4 28 93 144 395 56 210
## 5 5 40 108 204 470 10 252
## 6 6 55 120 279 530 0 210
## 7 7 73 130 359 580 0 120
## 8 8 93 137 454 620 0 45
## 9 9 118 143 554 650 0 10
## 10 10 148 148 674 674 0 1Identificación de la solución óptima
La solución óptima corresponde a la combinación factible con el mayor beneficio.
optima <- todos_resultados %>%
filter(factible) %>%
arrange(desc(beneficio_total)) %>%
slice(1)
optima## combinacion peso_total beneficio_total n_items factible
## 1 1,8,9,10 49 275 4 TRUEVisualización: Peso vs Número de Ítems
library(ggplot2)
ggplot(todos_resultados,
aes(x = n_items,
y = peso_total,
color = factible)) +
geom_point(alpha = 0.6) +
geom_point(
data = optima,
color = "darkblue",
size = 8,
shape = 13
) +
labs(
title = "Peso total vs número de ítems",
x = "Número de ítems",
y = "Peso total"
) +
theme_minimal()
Visualización: Beneficio vs Número de Ítems
ggplot(todos_resultados,
aes(x = n_items,
y = beneficio_total,
color = factible)) +
geom_point(alpha = 0.6) +
geom_point(
data = optima,
size = 8,
shape = 13
) +
labs(
title = "Beneficio total vs número de ítems",
x = "Número de ítems",
y = "Beneficio total"
) +
theme_minimal()
Análisis de combinaciones con cuatro ítems
resultados_4_items <- todos_resultados %>%
filter(n_items == 4) %>%
arrange(desc(factible),
desc(beneficio_total))
resultados_4_items## combinacion peso_total beneficio_total n_items factible
## 1 1,8,9,10 49 275 4 TRUE
## 2 1,2,4,8 50 270 4 TRUE
## 3 1,4,8,9 48 265 4 TRUE
## 4 2,4,9,10 49 265 4 TRUE
## 5 1,5,8,9 50 259 4 TRUE
## 6 4,6,8,9 50 255 4 TRUE
## 7 1,2,6,10 48 250 4 TRUE
## 8 2,4,8,10 46 250 4 TRUE
## 9 2,4,5,9 50 249 4 TRUE
## 10 1,6,9,10 46 245 4 TRUE
## 11 4,8,9,10 44 245 4 TRUE
## 12 2,5,8,10 48 244 4 TRUE
## 13 1,2,4,6 47 240 4 TRUE
## 14 5,8,9,10 46 239 4 TRUE
## 15 1,4,6,9 45 235 4 TRUE
## 16 1,2,5,6 49 234 4 TRUE
## 17 2,4,5,8 47 234 4 TRUE
## 18 1,2,4,10 41 230 4 TRUE
## 19 1,6,8,10 43 230 4 TRUE
## 20 1,5,6,9 47 229 4 TRUE
## 21 4,5,8,9 45 229 4 TRUE
## 22 1,4,9,10 39 225 4 TRUE
## 23 1,2,5,10 43 224 4 TRUE
## 24 1,4,6,8 42 220 4 TRUE
## 25 2,4,6,10 43 220 4 TRUE
## 26 1,5,9,10 41 219 4 TRUE
## 27 4,6,9,10 41 215 4 TRUE
## 28 1,2,4,5 42 214 4 TRUE
## 29 1,5,6,8 44 214 4 TRUE
## 30 2,5,6,10 45 214 4 TRUE
## 31 3,4,5,10 48 214 4 TRUE
## 32 1,4,8,10 36 210 4 TRUE
## 33 1,4,5,9 40 209 4 TRUE
## 34 5,6,9,10 43 209 4 TRUE
## 35 1,4,7,10 46 205 4 TRUE
## 36 1,5,8,10 38 204 4 TRUE
## 37 2,4,5,6 44 204 4 TRUE
## 38 4,6,8,10 38 200 4 TRUE
## 39 1,5,7,10 48 199 4 TRUE
## 40 4,5,6,9 42 199 4 TRUE
## 41 4,6,7,10 48 195 4 TRUE
## 42 1,4,5,8 37 194 4 TRUE
## 43 2,4,5,10 38 194 4 TRUE
## 44 5,6,8,10 40 194 4 TRUE
## 45 1,4,5,7 47 189 4 TRUE
## 46 4,5,9,10 36 189 4 TRUE
## 47 5,6,7,10 50 189 4 TRUE
## 48 4,5,6,8 39 184 4 TRUE
## 49 1,4,6,10 33 180 4 TRUE
## 50 4,5,6,7 49 179 4 TRUE
## 51 1,5,6,10 35 174 4 TRUE
## 52 4,5,8,10 33 174 4 TRUE
## 53 4,5,7,10 43 169 4 TRUE
## 54 1,4,5,6 34 164 4 TRUE
## 55 1,4,5,10 28 154 4 TRUE
## 56 4,5,6,10 30 144 4 TRUE
## 57 2,3,8,9 83 395 4 FALSE
## 58 2,3,7,9 93 390 4 FALSE
## 59 1,2,3,9 78 375 4 FALSE
## 60 2,3,7,8 90 375 4 FALSE
## 61 3,7,8,9 88 370 4 FALSE
## 62 2,3,6,9 80 365 4 FALSE
## 63 1,2,3,8 75 360 4 FALSE
## 64 1,2,3,7 85 355 4 FALSE
## 65 1,3,8,9 73 355 4 FALSE
## 66 2,3,9,10 74 355 4 FALSE
## 67 1,3,7,9 83 350 4 FALSE
## 68 2,3,6,8 77 350 4 FALSE
## 69 2,7,8,9 78 350 4 FALSE
## 70 2,3,4,9 73 345 4 FALSE
## 71 2,3,6,7 87 345 4 FALSE
## 72 3,6,8,9 75 345 4 FALSE
## 73 2,3,8,10 71 340 4 FALSE
## 74 3,6,7,9 85 340 4 FALSE
## 75 2,3,5,9 75 339 4 FALSE
## 76 1,2,8,9 63 335 4 FALSE
## 77 1,3,7,8 80 335 4 FALSE
## 78 2,3,7,10 81 335 4 FALSE
## 79 3,8,9,10 69 335 4 FALSE
## 80 1,2,3,6 72 330 4 FALSE
## 81 1,2,7,9 73 330 4 FALSE
## 82 2,3,4,8 70 330 4 FALSE
## 83 3,7,9,10 79 330 4 FALSE
## 84 1,3,6,9 70 325 4 FALSE
## 85 2,3,4,7 80 325 4 FALSE
## 86 2,6,8,9 65 325 4 FALSE
## 87 3,4,8,9 68 325 4 FALSE
## 88 3,6,7,8 82 325 4 FALSE
## 89 2,3,5,8 72 324 4 FALSE
## 90 1,2,3,10 66 320 4 FALSE
## 91 2,6,7,9 75 320 4 FALSE
## 92 3,4,7,9 78 320 4 FALSE
## 93 2,3,5,7 82 319 4 FALSE
## 94 3,5,8,9 70 319 4 FALSE
## 95 1,2,7,8 70 315 4 FALSE
## 96 1,3,9,10 64 315 4 FALSE
## 97 2,8,9,10 59 315 4 FALSE
## 98 3,7,8,10 76 315 4 FALSE
## 99 3,5,7,9 80 314 4 FALSE
## 100 1,2,3,4 65 310 4 FALSE
## 101 1,3,6,8 67 310 4 FALSE
## 102 1,7,8,9 68 310 4 FALSE
## 103 2,3,6,10 68 310 4 FALSE
## 104 2,7,9,10 69 310 4 FALSE
## 105 1,2,6,9 60 305 4 FALSE
## 106 1,3,4,9 63 305 4 FALSE
## 107 1,3,6,7 77 305 4 FALSE
## 108 2,4,8,9 58 305 4 FALSE
## 109 2,6,7,8 72 305 4 FALSE
## 110 3,4,7,8 75 305 4 FALSE
## 111 3,6,9,10 66 305 4 FALSE
## 112 1,2,3,5 67 304 4 FALSE
## 113 1,3,8,10 61 300 4 FALSE
## 114 2,3,4,6 67 300 4 FALSE
## 115 2,4,7,9 68 300 4 FALSE
## 116 6,7,8,9 70 300 4 FALSE
## 117 1,3,5,9 65 299 4 FALSE
## 118 2,5,8,9 60 299 4 FALSE
## 119 3,5,7,8 77 299 4 FALSE
## 120 1,2,9,10 54 295 4 FALSE
## 121 1,3,7,10 71 295 4 FALSE
## 122 2,7,8,10 66 295 4 FALSE
## 123 3,4,6,9 65 295 4 FALSE
## 124 2,3,5,6 69 294 4 FALSE
## 125 2,5,7,9 70 294 4 FALSE
## 126 1,2,6,8 57 290 4 FALSE
## 127 1,3,4,8 60 290 4 FALSE
## 128 2,3,4,10 61 290 4 FALSE
## 129 3,6,8,10 63 290 4 FALSE
## 130 7,8,9,10 64 290 4 FALSE
## 131 3,5,6,9 67 289 4 FALSE
## 132 1,2,4,9 53 285 4 FALSE
## 133 1,2,6,7 67 285 4 FALSE
## 134 1,3,4,7 70 285 4 FALSE
## 135 1,6,8,9 55 285 4 FALSE
## 136 2,4,7,8 65 285 4 FALSE
## 137 2,6,9,10 56 285 4 FALSE
## 138 3,4,9,10 59 285 4 FALSE
## 139 3,6,7,10 73 285 4 FALSE
## 140 1,3,5,8 62 284 4 FALSE
## 141 2,3,5,10 63 284 4 FALSE
## 142 1,2,8,10 51 280 4 FALSE
## 143 1,6,7,9 65 280 4 FALSE
## 144 3,4,6,8 62 280 4 FALSE
## 145 4,7,8,9 63 280 4 FALSE
## 146 1,2,5,9 55 279 4 FALSE
## 147 1,3,5,7 72 279 4 FALSE
## 148 2,5,7,8 67 279 4 FALSE
## 149 3,5,9,10 61 279 4 FALSE
## 150 1,2,7,10 61 275 4 FALSE
## 151 2,4,6,9 55 275 4 FALSE
## 152 3,4,6,7 72 275 4 FALSE
## 153 2,3,4,5 62 274 4 FALSE
## 154 3,5,6,8 64 274 4 FALSE
## 155 5,7,8,9 65 274 4 FALSE
## 156 1,3,6,10 58 270 4 FALSE
## 157 1,7,9,10 59 270 4 FALSE
## 158 2,6,8,10 53 270 4 FALSE
## 159 3,4,8,10 56 270 4 FALSE
## 160 2,5,6,9 57 269 4 FALSE
## 161 3,4,5,9 60 269 4 FALSE
## 162 3,5,6,7 74 269 4 FALSE
## 163 1,2,4,7 60 265 4 FALSE
## 164 1,6,7,8 62 265 4 FALSE
## 165 2,6,7,10 63 265 4 FALSE
## 166 3,4,7,10 66 265 4 FALSE
## 167 6,8,9,10 51 265 4 FALSE
## 168 1,2,5,8 52 264 4 FALSE
## 169 3,5,8,10 58 264 4 FALSE
## 170 1,3,4,6 57 260 4 FALSE
## 171 1,4,7,9 58 260 4 FALSE
## 172 2,4,6,8 52 260 4 FALSE
## 173 6,7,9,10 61 260 4 FALSE
## 174 1,2,5,7 62 259 4 FALSE
## 175 2,5,9,10 51 259 4 FALSE
## 176 3,5,7,10 68 259 4 FALSE
## 177 1,7,8,10 56 255 4 FALSE
## 178 2,4,6,7 62 255 4 FALSE
## 179 1,3,5,6 59 254 4 FALSE
## 180 1,5,7,9 60 254 4 FALSE
## 181 2,5,6,8 54 254 4 FALSE
## 182 3,4,5,8 57 254 4 FALSE
## 183 1,3,4,10 51 250 4 FALSE
## 184 4,6,7,9 60 250 4 FALSE
## 185 2,5,6,7 64 249 4 FALSE
## 186 3,4,5,7 67 249 4 FALSE
## 187 5,6,8,9 52 249 4 FALSE
## 188 1,4,7,8 55 245 4 FALSE
## 189 2,4,7,10 56 245 4 FALSE
## 190 6,7,8,10 58 245 4 FALSE
## 191 1,3,5,10 53 244 4 FALSE
## 192 5,6,7,9 62 244 4 FALSE
## 193 3,4,6,10 53 240 4 FALSE
## 194 4,7,9,10 54 240 4 FALSE
## 195 1,5,7,8 57 239 4 FALSE
## 196 2,5,7,10 58 239 4 FALSE
## 197 4,6,7,8 57 235 4 FALSE
## 198 1,3,4,5 52 234 4 FALSE
## 199 3,5,6,10 55 234 4 FALSE
## 200 5,7,9,10 56 234 4 FALSE
## 201 2,4,5,7 57 229 4 FALSE
## 202 5,6,7,8 59 229 4 FALSE
## 203 1,6,7,10 53 225 4 FALSE
## 204 4,7,8,10 51 225 4 FALSE
## 205 3,4,5,6 54 224 4 FALSE
## 206 4,5,7,9 55 224 4 FALSE
## 207 5,7,8,10 53 219 4 FALSE
## 208 1,4,6,7 52 215 4 FALSE
## 209 1,5,6,7 54 209 4 FALSE
## 210 4,5,7,8 52 209 4 FALSEVisualización tridimensional
library(plotly)##
## Adjuntando el paquete: 'plotly'## The following object is masked from 'package:ggplot2':
##
## last_plot## The following object is masked from 'package:stats':
##
## filter## The following object is masked from 'package:graphics':
##
## layoutfig <- plot_ly(
data = todos_resultados,
x = ~n_items,
y = ~peso_total,
z = ~beneficio_total,
color = ~factible,
colors = c("red","steelblue"),
type = "scatter3d",
mode = "markers"
)
figHistograma del peso
ggplot(todos_resultados,
aes(x = peso_total)) +
geom_histogram(
binwidth = 5,
fill = "steelblue",
color = "black"
) +
theme_minimal()
Histograma del beneficio
ggplot(todos_resultados,
aes(x = beneficio_total)) +
geom_histogram(
binwidth = 10,
fill = "gray",
color = "black"
) +
theme_minimal()
Analítica de datos: mapa de calor
tabla_mapa_calor <- todos_resultados %>%
mutate(
peso_cat = round(peso_total/5)*5,
beneficio_cat = round(beneficio_total/10)*10
) %>%
group_by(
peso_cat,
beneficio_cat
) %>%
summarise(
n_items = mean(n_items),
factible = any(factible),
.groups = "drop"
)ggplot(
tabla_mapa_calor,
aes(
x = peso_cat,
y = beneficio_cat,
fill = n_items
)
) +
geom_tile(color = "white") +
scale_fill_gradient(
low = "darkgoldenrod1",
high = "darkblue"
) +
theme_minimal()
Conclusiones
- Se generaron las 1023 combinaciones posibles.
- Se identificaron las combinaciones factibles y no factibles.
- Se encontró la solución óptima del problema de la mochila.
- Se exploró la relación entre peso, beneficio y número de ítems mediante visualizaciones bidimensionales y tridimensionales.
- El problema ilustra cómo la enumeración exhaustiva puede utilizarse para resolver problemas de optimización combinatoria de pequeña escala.