Le Monde puzzle [#958]

April 10, 2016
By

(This article was first published on R – Xi'an's Og, and kindly contributed to R-bloggers)

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

#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)) 

and

#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]}

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.

Filed under: Books, Kids, R Tagged: knapsack problem, Le Monde, mathematical puzzle, R

To leave a comment for the author, please follow the link and comment on their blog: R – Xi'an's Og.

R-bloggers.com offers daily e-mail updates about R news and tutorials on topics such as: Data science, Big Data, R jobs, visualization (ggplot2, Boxplots, maps, animation), programming (RStudio, Sweave, LaTeX, SQL, Eclipse, git, hadoop, Web Scraping) statistics (regression, PCA, time series, trading) and more...



If you got this far, why not subscribe for updates from the site? Choose your flavor: e-mail, twitter, RSS, or facebook...

Comments are closed.

Sponsors

Never miss an update!
Subscribe to R-bloggers to receive
e-mails with the latest R posts.
(You will not see this message again.)

Click here to close (This popup will not appear again)