Solution

This is my solution, written in Clojure, to the doll smuggler problem defined below. I attempted to modularize as much as I could to make it easier to add features to it if I ever need to. Here's a short description of each of the files:

• input/parse.clj
  • Can take a multi-line string and extract the problem data
  • Defines and maintains the problem variables
• input/file.clj
  • Reads a file and passes content to the parser
• input/web.clj
  • Takes POST parameters and passes them to the parser
• web/server.clj
  • Defines a webserver interface for the solver
• solver.clj
  • Using the data from the parser, solves the problem
  • Provides output methods for command line and web
• core.clj
  • the main method for the application
  • handles program arguments that define how the application is being run

Sample data from http://people.sc.fsu.edu/~jburkardt/datasets/knapsack_01/knapsack_01.html

For fun, I pushed this app to Heroku: http://njr-doll-smuggler.herokuapp.com

Usage

Requirements:

• Leiningen
• Input file formatted like the example in the problem below

To run:

$ lein run <path to data file>

Included data files:
  test/doll-smuggler/test/data/given.txt
  test/doll-smuggler/test/data/p1.txt
  test/doll-smuggler/test/data/p2.txt
  test/doll-smuggler/test/data/p3.txt

To run the webserver:

$ lein run -w

To run all tests:

$ lein test

Problem

You are a drug trafficker. Every day you meet with a different nice older lady (the mule) and find out how much weight she can carry in her handbag. You then meet with your supplier who has packed various drugs into a myriad of collectible porcelain dolls. Once packed with drugs, each of the precious dolls has a unique combination of weight and street value. Sometimes your supplier has more dolls than the nice lady can carry, though space in her handbag is never an issue. Your job is to choose which dolls the kind soul will carry, maximizing street value, while not going over her weight restriction.

Write a Clojure function which given:

• a set of dolls with a name and unique weight and value combination
• an overall weight restriction

Produces the optimal set of drug-packed porcelain dolls which:

• are within the total weight restriction
• maximize the total street value of drugs delivered

Include a set of executable high-level tests for your solution. The following is a set of inputs for which the correct result is known:

Input:

max weight: 400

available dolls:

name    weight value
luke        9   150
anthony    13    35
candice   153   200
dorothy    50   160
puppy      15    60
thomas     68    45
randal     27    60
april      39    40
nancy      23    30
bonnie     52    10
marc       11    70
kate       32    30
tbone      24    15
tranny     48    10
uma        73    40
grumpkin   42    70
dusty      43    75
grumpy     22    80
eddie       7    20
tory       18    12
sally       4    50
babe       30    10

Result:

packed dolls:

name    weight value
sally       4    50
eddie       7    20
grumpy     22    80
dusty      43    75
grumpkin   42    70
marc       11    70
randal     27    60
puppy      15    60
dorothy    50   160
candice   153   200
anthony    13    35
luke        9   150

Hints:

• use leiningen - https://github.com/technomancy/leiningen
• read this - http://en.wikipedia.org/wiki/Knapsack_problem
• find more interesting example data for test cases on the internets