Tree [efe1d1] default / examples / knapsack /
 History

Read Only access


File Date Author Commit
 README 2009-01-13 mtnyogi mtnyogi [31b2a6] - Fix for bug 2496575.
 __init__.py 2008-12-29 mtnyogi mtnyogi [5d0d34] - Changed second param to engine.__init__ to be...
 knapsack.krb 2008-04-28 mtnyogi mtnyogi [c593ff] 1. Made use of ':' in krb syntax deprecated
 knapsack.tst 2009-10-24 mtnyogi mtnyogi [3e0ae6] Cleaning up test scripts.
 test.py 2009-01-13 mtnyogi mtnyogi [31b2a6] - Fix for bug 2496575.

Read Me

This is the knapsack example taken from:

    http://www.ise.gmu.edu/~duminda/classes/fall03/set3.ppt starting on page 19

knapsack.krb
    This uses backward-chaining to solve the knapsack problem (see link above).
    The top-level goal is:

        legal_knapsack($Pantry, $Capacity, $Knapsack)

    $Pantry is a tuple of food items.  Each food item is: (name, weight,
    calories).

    $Capacity is the maximum weight capacity of the knapsack.

    $Knapsack is a subset of $Pantry whose total weight is <= $Capacity.

test.py
    run(pantry, capacity)
        Uses the legal_knapsack goal to enumerate all of the possible
        knapsacks within the stated capacity.  Returns the total_calories and
        knapsack of the answer with most calories.

        The final example on page 36 at the site above would be:

        >>> from examples.knapsack import test
        >>> test.run((('bread',4,9200),
                      ('pasta',2,4500),
                      ('peanutButter',1,6700),
                      ('babyFood',3,6900)),
                     4)