Le Monde puzzle [#958]
A knapsack Le Monde mathematical puzzle:
Given n packages weighting each at most 5.8kg for a total weight of 300kg, is it always possible to allocate these packages to 12 separate boxes weighting at most 30kg each? weighting at most 29kg each?
This can be checked by brute force using the following R code
[sourcecode language=”r” gutter=”false”]
#generate packages
paca=runif(1,0,5.8)
while (sum(paca)<300){
paca=c(paca,runif(1,0,5.8))}
paca=paca[-length(paca)]
paca=c(paca,300-sum(paca))
[/sourcecode]
and
[sourcecode language=”r” gutter=”false”]
#check if they can be partitioned into
#12 groups of weight less than 30
box=vector(mode="list",length=12)
#random allocation
alloc=sample(1:12,length(paca),rep=TRUE)
content=rep(0,12)
for (i in 1:12){
box[[i]]=paca[alloc==i]
content[i]=sum(box[[i]])}
content=content*(content>0)
#wrong allocation
while (max(content)>30){
i=sample(1:12,1,prob=content)
j=sample(1:length(box[[i]]),1,prob=box[[i]])
#reallocation
k=sample(1:12,1,prob=max(content)-content)
while (k==i){
k=sample(1:12,1,prob=max(content)-content)}
content[i]=content[i]-box[[i]][j]
content[i]=content[i]*(content[i]>0)
content[k]=content[k]+box[[i]][j]
box[[k]]=c(box[[k]],box[[i]][j])
box[[i]]=box[[i]][-j]}
[/sourcecode]
repeatedly and could not find an endless while loop. (Empty boxes sometimes lead to negative contents, hence my fix setting negative contents to zero.) But neither did I find an issue when the upper bound on the weight is 29kg… So it is either possible or rarely impossible! The R code immediately gets stuck when setting the bound at 25kg.
After reading the solution of April 13 in Le Monde, it appears that there is a counter example for the 29kg limit, namely 60 packages weighting 4.91kg plus one package weighting 5.4kg, since the first 60 packages fit inside 12 boxes and the last one is left out.
April 11, 2016 at 1:38 pm
Here is a possible solution using Genetic Algorithms:
# generate packages
set.seed(123)
paca = runif(1,0,5.8)
while(sum(paca) < 300)
{ paca = c(paca, runif(1,0,5.8)) }
paca = paca[-length(paca)]
paca = c(paca,300-sum(paca))
n = length(paca) # 104 packages generated
weightBox = 30 # constraint on the maximum weight of a box
# fitness function to optimise
knapsack <- function(x)
{
x = floor(x) # assignment of packages to boxes (integer 1,…,12)
w = tapply(paca, x, sum) # weight of each box
wdiff = (w – weightBox)
# penalised fitness function (more heavily max weight constraint violation)
-sum(ifelse(wdiff < 0, abs(wdiff), 100*wdiff^2))
}
library(GA)
GA = ga(type = "real-value",
fitness = knapsack, min = rep(1,n), max = rep(13, n),
maxiter = 1000, run = 200, popSize = 50)
plot(GA)
summary(GA)
x = floor(GA@solution[1,])
table(x) # allocation of packages in each box
(w = tapply(paca, x, sum)) # weight of each box
sum(w) # sum of all the boxes
April 11, 2016 at 10:02 pm
Thanks, it does indeed provide an answer as well when weightBox = 29!