cutrod

cutrod.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Modified from http://stackoverflow.com/questions/16608661/python-implementing-rod-cutting-algorithm"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def cut_rodR(p, n):\n",
    "    if n==0:\n",
    "        return 0\n",
    "    q = float('-inf')\n",
    "    for i in range(n):\n",
    "        q = max(q, p[i] + cut_rodR(p, n-1-i))\n",
    "    return q"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "n= 4 cut_rodR(.., 4 )= 10 time 0.00011379540061117613 seconds process time\n",
      "n= 22 cut_rodR(.., 22 )= 65 time 4.283099644468398 seconds process time\n",
      "[4.268357213245469, 4.254938443800482, 4.2315874695459, 4.230859653129492, 4.260817477709139]\n"
     ]
    }
   ],
   "source": [
    "p = [1,5,8,9,10,17,17,20,24,30,31,35,38,39,40,47,47,50,54,60,61,65,68,69,70,77,77,80,84,90,91,95,98,99,100,107,107,110,114,120,121,125,128,129,130,137,137,140,144,150]\n",
    "\n",
    "n = 4\n",
    "import time\n",
    "t0 = time.clock()\n",
    "k = cut_rodR(p, n)\n",
    "tf =time.clock()\n",
    "print(\"n=\",n,\"cut_rodR(..,\",n,\")=\",k,\"time\",tf - t0, \"seconds process time\")\n",
    "\n",
    "n = 22\n",
    "import time\n",
    "t0 = time.clock()\n",
    "k = cut_rodR(p, n)\n",
    "tf =time.clock()\n",
    "print(\"n=\",n,\"cut_rodR(..,\",n,\")=\",k,\"time\",tf - t0, \"seconds process time\")\n",
    "\n",
    "import timeit\n",
    "print(timeit.repeat(\"cut_rodR(p, n)\", \"from __main__ import cut_rodR,p,n\",repeat=5,number=1))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Modified from https://github.com/Tayacan/AD-examples-python/blob/master/cut-rod.py"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def cut_rod(p,n):\n",
    "    \"\"\"p is the list of prices, n is the length of the rod.\"\"\"\n",
    "    r = [0] * (n+1) # Holds the max revenue of each length\n",
    "    s = [0] * (n+1)\n",
    "    r[0] = 0\n",
    "    for j in range(1,n+1):\n",
    "        q = float('-inf')\n",
    "        for i in range(1,j+1):\n",
    "                if q < p[i] + r[j - i]:\n",
    "                    q = p[i] + r[j - i]\n",
    "                    s[j] = i\n",
    "        r[j] = q\n",
    "    return r,s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def cut_rod_solution(p,n):\n",
    "    r,s = cut_rod(p,n)\n",
    "    print(r)\n",
    "    print(s)\n",
    "    while n > 0:\n",
    "        print(n,s[n],n-s[n],r[n],p[s[n]],r[n]-p[s[n]])\n",
    "        n -= s[n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[0, 1, 5, 8, 10]\n",
      "[0, 1, 2, 3, 2]\n",
      "4 2 2 10 5 5\n",
      "2 2 0 5 5 0\n",
      "None\n",
      "[3.832692312144559e-05, 2.7658604317082336e-05, 2.7658604317082336e-05, 2.726348139603374e-05, 2.726348139603374e-05]\n",
      "[0, 1, 5, 8, 10, 13, 17, 18, 22, 25, 30, 31, 35, 38, 40, 43, 47, 48, 52, 55, 60, 61, 65, 68, 70, 73, 77, 78, 82, 85, 90, 91, 95, 98, 100, 103, 107, 108, 112, 115, 120, 121, 125, 128, 130, 133, 137, 138, 142, 145, 150]\n",
      "[0, 1, 2, 3, 2, 2, 6, 1, 2, 3, 10, 1, 2, 3, 2, 2, 6, 1, 2, 3, 10, 1, 2, 3, 2, 2, 6, 1, 2, 3, 10, 1, 2, 3, 2, 2, 6, 1, 2, 3, 10, 1, 2, 3, 2, 2, 6, 1, 2, 3, 10]\n",
      "50 10 40 150 30 120\n",
      "40 10 30 120 30 90\n",
      "30 10 20 90 30 60\n",
      "20 10 10 60 30 30\n",
      "10 10 0 30 30 0\n",
      "None\n",
      "[0.0009830658219449617, 0.0007914312063306284, 0.0007874799771450114, 0.00078787510006606, 0.0007890604688221003]\n"
     ]
    }
   ],
   "source": [
    "import timeit\n",
    "p = [0,1,5,8,9,10,17,17,20,24,30,31,35,38,39,40,47,47,50,54,60,61,65,68,69,70,77,77,80,84,90,91,95,98,99,100,107,107,110,114,120,121,125,128,129,130,137,137,140,144,150]\n",
    "\n",
    "n = 4\n",
    "print(cut_rod_solution(p,n))\n",
    "print(timeit.repeat(\"cut_rod(p,n)\", \"from __main__ import cut_rod,p,n\",number =1,repeat=5))\n",
    "\n",
    "n = 50\n",
    "print(cut_rod_solution(p,n))\n",
    "print(timeit.repeat(\"cut_rod(p,n)\", \"from __main__ import cut_rod,p,n\",number =1,repeat=5))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.4.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}