Loading presentation...

Present Remotely

Send the link below via email or IM


Present to your audience

Start remote presentation

  • Invited audience members will follow you as you navigate and present
  • People invited to a presentation do not need a Prezi account
  • This link expires 10 minutes after you close the presentation
  • A maximum of 30 users can follow your presentation
  • Learn more about this feature in our knowledge base article

Do you really want to delete this prezi?

Neither you, nor the coeditors you shared it with will be able to recover it again.


The on-line knapsack problem

master degree work to present combinatoric problem

Dymitr Szemiel

on 5 October 2011

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of The on-line knapsack problem

The online knapsack problem Comparison of algorithms for
the online knapsack problem Supervisor:
prof. Maciej M. Sysło Dzmitry Shemel
Index Nr.: 238766 What is
knaspsack problem? weight Choose items ...then pack them into a knapsack... ..? we dont know in advance all the items
new item arrives in time and we are to decide whenever pack it or not weight = cost Removable case There are diffrent types of the online knapsack problem weighted and unweighted cases
removable case weight Unweighted case = = = = cost Fill the knapsack and maximize profit = = Fill knapsack
till it is full Solutions for the online knapsack ? ? ? ? ? ? ? ? ? Greedy ( Threshold ) (cost/weight) > T ? ? Yes Put item into a
knapsack ?... No,
throw item away The removable online knapsack (X. Han algorithm) 1. Divide items into groups by size 2. In each group remove item with lowest cost
(if needed) 3. Merge items
into one group Greedy
(unweighted case with removable condition) 1. Arrange the items in the knapsack in increasing order 2.If new item is bigger the the smallest
it will fit in knapsack instead of easiest item Golden ratio
(unweighted case with removable condition) 1. Divide items into four groups: 2. Three possible patterns for the items in the knapsack: Implementation and experiments Weighted algorithms Unweighted algorithms Thank you for your attention :) CONCLUSIONS
Full transcript