Thursday, May 17, 2012

Knapsack Algorithm Shortcut Method

The knapsack problem or rucksack problem is a problem in combinatorial optimization: Given a set of items, each with a weight and a value, determine the number of each item to include in a collection so that the total weight is less than or equal to a given limit and the total value is as large as possible. It derives its name from the problem faced by someone who is constrained by a fixed-size knapsack and must fill it with the most valuable items.
The main goal of Knapsack  is:
  • You have a knapsack that has capacity (weight) W.
  • You have several items I1,…,In.
  • Each item Ij has a weight wj and a benefit bj.You want to place a certain number of copies of each item Ij in the knapsack so that: The knapsack weight capacity is not exceeded and The total benefit is maximal.

There is a Shortcut Method  for Knapsack Algorithm , see the video:  

2 comments em “Knapsack Algorithm Shortcut Method”

Post a Comment

Give your valuable Comment...


Programming, Data Structures & Algorithms Copyright © 2011 -- Template created by JAK -- Powered by Blogger