Saturday, August 13, 2011

Knapsack

You have n types of items, where the ith item type has an integer size si and a real value vi. You need to fill a knapsack of total capacity C with a selection of items of maximum value.

1 comment:

  1. I love the NP complete problems...
    In my life I understood that the optimum is unreachable, and sometimes "strike a balance" between efforts and results is the all the best we can do!
    ...The good old Metropolis algorithm follows exactly this principle and so I love it!.
    http://textanddatamining.blogspot.com/

    ReplyDelete