The Knapsack Problem

2009-07-10 20:30:00 Allan Engelhardt wrote in CYBAEA Data and Analysis:

David posts a question about how to solve this knapsack problem using the R statistical computing and analysis platform. My reply in the comments seems to have disappeared for a while so here is my proposed solution. See David’s blog for my earlier proposed solution with a very common error.

## http://blog.revolution-computing.com/2009/07/because-its-friday-the-knapsack-problem.html
appetizer.solution <- local (
function (target) {
  app <- c(2.15, 2.75, 3.35, 3.55, 4.20, 5.80)
  r <- 2L
  repeat {
	c <- gtools::combinations(length(app), r=r, v=app, repeats.allowed=TRUE)
	s <- rowSums(c)
	if ( all(s > target) ) {
	  print("No solution found")
	  break
	}
	x <- which( abs(s-target) < 1e-4 )
	if ( length(x) > 0L ) {
	  cat("Solution found: ", c[x,], "\n")
	  break
	}
	r <- r + 1L
  }
})

appetizer.solution(15.05)
# Solution found:  2.15 3.55 3.55 5.8

Brute force works, it just doesn’t scale well. (Note that 7×2.15 is another solution.)

Bookmark on Delicious

Share on LinkedIn

Share on reddit

Subscribe to CYBAEA Data and Analysis

Jump to comments.

Popular right now

Recent blog entries

Commercial Analytics: The Capabilities

2011-10-05 21:43:00 Allan Engelhardt wrote in CYBAEA Journal:

Commercial Analytics is the kind that makes money. From data to dollars, insights to income, this is all about how to run the business better. To do it and to do it well you need certain capabilities in place. This article builds a map of those business capabilities to help you assess, understand, and plan your business.

Usually we talk about this and we are happy to talk to you about it (just contact us) but we recently had occasion to make a slide pack that covered some of the materials as a stand-alone presentation. This article is based on that pack which is also available for download.

5 common pitfalls of commercial analytics projects

2011-09-05 17:25:00 Allan Engelhardt wrote in CYBAEA Journal:

We have seen data mining and other analytics projects fail; we have seen insights teams unable to deliver the insights needed to actually improve the business; we have seen marketing teams unable to use data effectively to guide and quantify their activities; we have seen business leaders who are sitting on piles of data but are effectively flying blind because they can not get from the data to the knowledge they need to inform their decisions.

Below we have listed five common pitfalls of analytics in a commercial environment, their warning signs, and what you can do differently.

Inflow segmentation – measuring new customers by value not volume

2011-01-06 20:35:00 Allan Engelhardt wrote in CYBAEA Journal:

Do you have accurate and timely analysis of the quality of the customers you are acquiring? Most companies carefully track the quantity of new customers by the hour, day, or certainly the week, but it is still less common to track the quality of the inflow as it happens. It is interesting to know that we have acquired, say, 1000 new customers today, but so very much more informative to know that this inflow will bring in £22,000 of revenues over the next year at 35% margin. Break it down by channel and product to see who is performing and who is not, and I as a marketing manager get really excited: I have the tools to do my job!

Monitoring the quality of the inflow and understanding the reasons for change is essential. After all, if your new customers are of lower quality than your existing base, then you are setting your company up for difficulties over many years to come.

Considering how much companies typically spend acquiring each new customer, this really should be a no-brainer. And yet many companies are completely unnecessarily stuck at reporting sales by volume instead of value.

R versus SAS/SPSS in corporations

2011-10-28 11:10:00 Allan Engelhardt wrote in CYBAEA Data and Analysis:

A recent question on one of the LinkedIn groups about the advantages of using R over commercial tools like SAS or IBM SPSS Modeller drew lots of comments for R. We like R a lot and we use it extensively, but I also wanted to balance the discussion. R is great, but looking at commercial organizations near the end of 2011 it is not necessarily the right choice to make.

Friday quote: what is the question to which this number is the answer?

2011-08-26 09:05:00 Allan Engelhardt wrote in CYBAEA Data and Analysis:

John Kay muses on interpreting statistical data:

Always ask of such data “what is the question to which this number is the answer?”. “Earnings before interest, tax, depreciation and amortisation on a like-for-like basis before allowance for exceptional restructuring costs” is the answer to the question “what is the highest profit number we can present without attracting flat disbelief?”.

A warning on the R save format

2011-08-23 07:20:00 Allan Engelhardt wrote in CYBAEA Data and Analysis:

The save() function in the R platform for statistical computing is very convenient and I suspect many of us use it a lot. But I was recently bitten by a “feature” of the format which meant I could not recover my data.

I recommend that you save data in a data format (e.g. CSV or CDF), not using the save() function which is really for objects (data and code). What is your approach?

4 easy steps to make Mason utf-8 Unicode clean with Apache, mod_perl, and DBI

2009-01-28 17:57:00 Allan Engelhardt wrote in CYBAEA Technology Notes:

This is a note for people who are using the Mason system for high-performance, dynamic web site authoring with Apache, mod_perl, and a relational database like PostgreSQL accessed through DBI, and who want to be utf-8 Unicode clean in all their data.

You want to be able to write accented letters in any language in your web pages. You want your users to be able to enter any characters in web forms, and you want that data to get in and out of your relational database and still display correctly and be handled correctly by perl.

That is, unfortunately, not how it works out of the box, at least not on Red Hat Enterprise Linux 5 or on Fedora 10. This article shows how we made it work right.