Send the link below via email or IMCopy
Present to your audienceStart 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.
Make your likes visible on Facebook?
You can change this under Settings & Account at any time.
The on-line knapsack problem
Transcript of The on-line knapsack problem
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