Hi David, On Mon, Jul 6, 2009 at 10:34 PM, David Joyner<wdjoy...@gmail.com> wrote:
<SNIP> > I'm not an expert but did find this ((essentially vacuous) page: > http://www.coin-or.org/SYMPHONY/branchandcut/MCKP/ > and the knapsack problem is listed among the applications of Symphony: > http://www.coin-or.org/SYMPHONY/branchandcut/applications.htm > I could find no examples. Thank you for the pointer. <SNIP> >> So my question is: Do folks agree or disagree with me Cythonizing >> >> sage/numerical/knapsack.py >> >> and implement further algorithms in Cython? > > > Well, I can't see an argument against making it faster:-) > However, it would be nice if you could add some brute force code to > actually solve an instance of the knapsack problem, for example > the burgler problem at > http://webspace.ship.edu/thbrig/DynamicProgramming/Knapsack%20Program/index.html At the moment, my priority is to implement as many algorithms as I can/understand. On that list are certainly a greedy algorithm and a dynamic programming algorithm. Somewhere down the list are more efficient algorithms for other types of knapsack problems. My main references are [1] S. Martello and P. Toth. Knapsack Problems. http://www.or.deis.unibo.it/knapsack.html [2] H. Kellerer, U. Pferschy and D. Pisinger. Knapsack problems. > I probably would not use your code for teaching nut I know people > who probably would if thee were enough examples to help them with the syntax. -- Regards Minh Van Nguyen --~--~---------~--~----~------------~-------~--~----~ To post to this group, send email to sage-devel@googlegroups.com To unsubscribe from this group, send email to sage-devel-unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/sage-devel URLs: http://www.sagemath.org -~----------~----~----~----~------~----~------~--~---
