Welcome to knapsack-api's documentation!
========================================
Post a problem
--------------
**POST** /api/problems

Description
+++++++++++
Submit a new problem to the resolver

Request body
++++++++++++
Example::

   {
     "objects": [
         { "name": "o1", "value": 5, "weight": 2},
         { "name": "o2", "value": 8, "weight": 3},
         { "name": "o3", "value": 14, "weight": 5},
         { "name": "o4", "value": 6, "weight": 2},
         { "name": "o5", "value": 13, "weight": 4},
         { "name": "o6", "value": 17, "weight": 6},
         { "name": "o7", "value": 10, "weight": 3},
         { "name": "o8", "value": 4, "weight": 1}
     ],
     "sack": {
        "max-weight": 12
     }
   }

Response body
+++++++++++++
Example::

   {
     "link": "http://mydomain.org/api/problem/0",
     "objects": [
        { "name": "o8", "value": 4, "weight": 1},
        { "name": "o7", "value": 10, "weight": 3},
        { "name": "o5", "value": 13, "weight": 4},
        { "name": "o4", "value": 6, "weight": 2},
        { "name": "o1", "value": 5, "weight": 2}
     ],
     "sack": {
        "weight": 12
     }
   }

> pip install requests

if __name__ == "__main__":
  data = {
    "objects": [
      { "name": "o1", "value": 5, "weight": 2},
      { "name": "o2", "value": 8, "weight": 3},
      { "name": "o3", "value": 14, "weight": 5},
      { "name": "o4", "value": 6, "weight": 2},
      { "name": "o5", "value": 13, "weight": 4},
      { "name": "o6", "value": 17, "weight": 6},
      { "name": "o7", "value": 10, "weight": 3},
      { "name": "o8", "value": 4, "weight": 1},
    ],
    "sack": {"max-weight": 12}
  }

  url = "http://localhost:8888/api/problems"
  result = requests.post(url, data=json.dumps(data))
  result = json.loads(result.text)
  print(json.dumps(result, indent=4))

  link = result["link"]
  result = requests.get(link)
  result = json.loads(result.text)
  print(json.dumps(result, indent=4))

def resolve(items, sack):
  max_w = sack["max-weight"]

  v = [[(0, False)] * (max_w+1) for i in xrange(len(items))]
    
  for w in xrange(max_w+1):
    if w < items[0]["weight"]:
      v[0][w] = (0, False)
    else:
      v[0][w] = (items[0]["value"], True)

  for k in xrange(1, len(items)):
    for w in xrange(max_w+1):
      if w < items[k]["weight"]:
        v[k][w] = (v[k-1][w][0], False)
      else:
        old = (v[k-1][w][0], False)
        new = (v[k-1][w-items[k]["weight"]][0]+items[k]["value"], True)
        v[k][w] = max(old, new)
                
  result = []
  w = max_w
  for k in xrange(len(items)-1, -1, -1):
    if v[k][w][1]:
      result.append(items[k])
      w -= items[k]["weight"]

  return result

class ProblemsHandler(tornado.web.RequestHandler):
  def initialize(self, storage):
    self.storage = storage

  def post(self):
    data = json.loads(self.request.body)
    prob_id = len(storage)
    result = dict()
    storage[prob_id] = result
    url = "http://localhost:8888/api/problems/%s"%(prob_id)
    result["link"] = url
    result["objects"] = resolve(data["objects"], data["sack"])
    result["sack"] = data["sack"]
    self.write(json.dumps(result))

class ProblemHandler(tornado.web.RequestHandler):
  def initialize(self, storage):
    self.storage = storage

  def get(self, prob_id):
    self.write(json.dumps(self.storage[int(prob_id)]))

storage = dict()
application = tornado.web.Application([
    (r"/api/problems", ProblemsHandler, dict(storage=storage)),
    (r"/api/problems/(.*)", ProblemHandler,  dict(storage=storage)),
])

if __name__ == "__main__":
    application.listen(8888)
    tornado.ioloop.IOLoop.instance().start()

[unix_http_server]
file=/tmp/supervisor.sock

[supervisord]
logfile=/tmp/supervisord.log
loglevel=info
pidfile=/tmp/supervisord.pid
nodaemon=false

[rpcinterface:supervisor]
supervisor.rpcinterface_factory = supervisor.rpcinterface:make_main_rpcinterface

[supervisorctl]
serverurl=unix:///tmp/supervisor.sock

[program:knapsack-api]
command=$VIRTUALENV/bin/python application.py
process_name=knapsack
numprocs=1

server {
  listen 80;
  location ~ ^/api(.*)$ {
    proxy_pass http://127.0.0.1:8888/api$1$is_args$args;
  }
}