A particularly geeky strip from XKCD:

Any suggestions on how one might solve this problem in R?

XKCD: NP-Complete

« Benford's Law, Zipf's Law and the Pareto Distribution | Main | Thoughts on UseR! 2009 »

TrackBack URL for this entry:

http://www.typepad.com/services/trackback/6a010534b1db25970b0115705ca0e9970c

Listed below are links to weblogs that reference Because it's Friday: The Knapsack Problem:

You can follow this conversation by subscribing to the comment feed for this post.

The comments to this entry are closed.

Got comments or suggestions for the blog editor?

Email David Smith.

Email David Smith.

- academia
- advanced tips
- announcements
- applications
- beginner tips
- big data
- courses
- current events
- data science
- developer tips
- events
- finance
- government
- graphics
- high-performance computing
- life sciences
- open source
- other industry
- packages
- popularity
- predictive analytics
- profiles
- R
- R is Hot
- random
- Revolution
- Rmedia
- roundups
- sports
- statistics
- user groups

- CRAN

Packages for R - inside-R.org, the R Community Site

Sponsored by Revolution Analytics - Revolution Analytics

Information about Revolution R - Download Revolution R

Free, high-performance distribution of R - Revolution R forum

Questions and discussions about Revolution R - R Project site

Information about the R project

- FlowingData

Modern data visualization - One R Tip A Day

Code examples for graphics and analysis - Probability and statistics blog

Monte Carlo simulations in R - R Bloggers

Daily news and tutorials about R, contributed by R bloggers worldwide. - R Project group on analyticbridge.com

Community and discussion forum - Statistical Modeling, Causal Inference, and Social Science

Andrew Gelman's statistics blog - The Dataists

Innovative and practical data analysis methodology.

Brute force works for me:

Posted by: Allan Engelhardt | July 10, 2009 at 13:14

I canâ€™t believe I just wrote that. Must be the heat. This must be

the most elementarymistake in numerical analysis. Try this version instead:I'll go and kill myself now....

Posted by: Allan Engelhardt | July 10, 2009 at 13:40

Wait a minute, if repeats are allowed, then you have to have different utilities for second replicate. Decreasing marginal returns. Where are you getting your item utilities from?

Posted by: Chris P | July 12, 2009 at 16:33

A marginally better solution exists by reducing the problem 'dynamically.' I have implemented this as a program for the subset sum problem but this versio n assumed repetitions are not allowed. An adaptation to allow repeats should still work.

The program and a pdf version of a flowchart for it are available at;

www.cybase.co.uk/wlcs/Software.html

Posted by: Stephen Le Guen | August 19, 2009 at 04:47

Looking at the answer given by Allan the solution is incorrect!

3.55 + 5.80 + 5.80 = 15.15

Also the answer above totals 15.15, but the original problem found no solution only as 15.15, he apparently tried again with the second target sum.

My program does not search for solutions with duplicates, but allows duplicate alues to be entered. Doubling up eaxh entry finds the solution

2.15 + 3.55 + 3.55 + 5.80 = 15.05

but the values are entered as whole numbers.

Steve

Posted by: Stephen Le Guen | August 21, 2009 at 06:12