[This article was first published on

Want to share your content on R-bloggers? click here if you have a blog, or here if you don't.

**R – Xi'an's Og**, and kindly contributed to R-bloggers]. (You can report issue about the content on this page here)Want to share your content on R-bloggers? click here if you have a blog, or here if you don't.

**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?

**T**his 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 about learning R and many other topics. Click here if you're looking to post or find an R/data-science job.

Want to share your content on R-bloggers? click here if you have a blog, or here if you don't.