際際滷

際際滷Share a Scribd company logo

knapsack problem

Download as PPTX, PDF
A
Adnan Malak

The document provides an introduction to the knapsack problem. It defines the knapsack problem as determining 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, given a set of items each with a mass and value. It notes there are two versions: the 0-1 knapsack problem, where items are indivisible and you either take an item or not, and the fractional knapsack problem, where items are divisible and you can take fractions of items.

1 of 19
Downloaded 94 times
BRIEF INTRO TO KNAPSACK PROBLEM
Knapsack A 1998 study of the Stony Brook University Algorithm Repository showed that, out of 75 algorithmic problems, the knapsack problem was the 18th most popular and the 4th most needed after kd-trees, suffix trees, and the bin packing problem
Knapsack problem Given a set of items, each with a mass 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.
Given some items, pack the knapsack to get the maximum total value. Each item has some weight and some value. Total weight that we can carry is no more than some fixed number W. So we must consider weights of items as well as their values. Item # Weight Value 1 1 8 2 3 6 3 5 5 Knapsack problem
which boxes should be chosen to maximize the amount of money while still keeping the overall weight under or equal to 15 kg?
Answer: 3 yellow boxes and 3 grey boxes .
Problem A thief breaks into a house. Around the thief are various objects: a diamond ring, a silver candelabra, a Bose Wave Radio (tm), a large portrait of Elvis Presley painted on a black velvet background (a "velvet-elvis"), and a large tiffany crystal vase. The thief has a knapsack that can only hold a certain capacity. Each of the items has a value and a size, and cannot hold all of the items in the knapsack.
Item Size Value 1-Ring 1 15 2-Candelabra 5 10 3-Radio 3 9 4-Elvis 4 5 The problem is, which items should the thief take? If the knapsack were large enough, the thief could take all of the items and run. But, that is not the case (the problem states that the knapsack cannot hold all of the items). There are three types of "thieves" that we shall consider: a greedy thief, a foolish and slow thief, and a wise thief. Each of these thieves have a knapsack that can old a total size of 8.
The greedy thief breaks into the window, and sees the items. He makes a mental list of the items available, and grabs the most expensive item first. The ring goes in first, leaving a capacity of 7, and a value of 15. Next, he grabs the candelabra, leaving a knapsack of size 2 and a value of 25. No other items will fit in his knapsack, so he leaves. The foolish and slow thief climbs in the window, and sees the items. This thief was a programmer, downsized as part of the "dot-bomb" blowout. Possessing a solid background in Boolean logic, he figures that he can simply compute all combinations of the objects and choose the best. So, he starts going through the binary combinations of objects - all 2^5 of them. While he is still drawing the truth table, the police show up, and arrest him. Although his solution would certainly have given him the best answer, it just took long to compute.
The wise thief appears, and observes the items. He notes that an empty knapsack has a value of 0. Further, he notes that a knapsack can either contain each item, or not. Further, his decision to include an item will be based on a quick calculation - either the knapsack with some combination of the previous items will be worth more, or else the knapsack of a size that will fit the current item was worth more. So, he does this quick computation, and figures out that the best knapsack he can take is made up of items 1,3, and 4, for a total value of 29.
Knapsack problem There are two versions of the problem: 1. 0-1 knapsack problem Items are indivisible; you either take an item or not. Some special instances can be solved with dynamic programming Exhibit No greedy choice property. No greedy algorithm exists. Exhibit optimal substructure property. Only dynamic programming algorithm exists. .
1. Fractional knapsack problem Items are divisible: you can take any fraction of an item Exhibit greedy choice property. Greedy algorithm exists. Exhibit optimal substructure property
0-1 Knapsack Problem The thief wants to steal n items The ith item weighs wi and has value vi Take the most valuable load, limit of W pounds This is called the 0-1 version of the problem because there are no fractions. The thief must take the whole item or leave it behind.
Both the 0-1 Knapsack Problem and the Fractional Knapsack Problem have optimal substructure. If we remove item j from the optimal load, the remaining problem must be optimal for the remaining W - wj pounds for the overall solution to be optimal. The greedy solution for the Fractional Knapsack Problem does not work here
Example: Item Value Weight 1 60 10 2 100 20 3 120 30 W = 50 The greedy solution would select 1, leaving 40 pounds. At this point if we pick items 1 and 2 the total value is 160. If we pick items 1 and 3 the total value is 180. The optimal solution is to pick items 2 and 3. The total value of this solution is 220
Example: Fractional Knapsack Problem A thief considers taking W pounds of loot. The loot is in the form of n items, each with weight wi and value vi. Any amount of an item can be put in the knapsack as long as the weight limit W is not exceeded.
Question: How much of which items should the thief take to maximize the value of the loot? Greedy Algorithm: Take as much of the item with the highest value per pound (vi/wi) as you can. If you run out of that item, take from the next highest (vi/wi) item. Continue until knapsack is full.
Thank You
QUESTIONS ANSWER SESSION?

More Related Content

knapsack problem

  • 2. Knapsack A 1998 study of the Stony Brook University Algorithm Repository showed that, out of 75 algorithmic problems, the knapsack problem was the 18th most popular and the 4th most needed after kd-trees, suffix trees, and the bin packing problem
  • 3. Knapsack problem Given a set of items, each with a mass 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.
  • 4. Given some items, pack the knapsack to get the maximum total value. Each item has some weight and some value. Total weight that we can carry is no more than some fixed number W. So we must consider weights of items as well as their values. Item # Weight Value 1 1 8 2 3 6 3 5 5 Knapsack problem
  • 5. which boxes should be chosen to maximize the amount of money while still keeping the overall weight under or equal to 15 kg?
  • 6. Answer: 3 yellow boxes and 3 grey boxes .
  • 7. Problem A thief breaks into a house. Around the thief are various objects: a diamond ring, a silver candelabra, a Bose Wave Radio (tm), a large portrait of Elvis Presley painted on a black velvet background (a "velvet-elvis"), and a large tiffany crystal vase. The thief has a knapsack that can only hold a certain capacity. Each of the items has a value and a size, and cannot hold all of the items in the knapsack.
  • 8. Item Size Value 1-Ring 1 15 2-Candelabra 5 10 3-Radio 3 9 4-Elvis 4 5 The problem is, which items should the thief take? If the knapsack were large enough, the thief could take all of the items and run. But, that is not the case (the problem states that the knapsack cannot hold all of the items). There are three types of "thieves" that we shall consider: a greedy thief, a foolish and slow thief, and a wise thief. Each of these thieves have a knapsack that can old a total size of 8.
  • 9. The greedy thief breaks into the window, and sees the items. He makes a mental list of the items available, and grabs the most expensive item first. The ring goes in first, leaving a capacity of 7, and a value of 15. Next, he grabs the candelabra, leaving a knapsack of size 2 and a value of 25. No other items will fit in his knapsack, so he leaves. The foolish and slow thief climbs in the window, and sees the items. This thief was a programmer, downsized as part of the "dot-bomb" blowout. Possessing a solid background in Boolean logic, he figures that he can simply compute all combinations of the objects and choose the best. So, he starts going through the binary combinations of objects - all 2^5 of them. While he is still drawing the truth table, the police show up, and arrest him. Although his solution would certainly have given him the best answer, it just took long to compute.
  • 10. The wise thief appears, and observes the items. He notes that an empty knapsack has a value of 0. Further, he notes that a knapsack can either contain each item, or not. Further, his decision to include an item will be based on a quick calculation - either the knapsack with some combination of the previous items will be worth more, or else the knapsack of a size that will fit the current item was worth more. So, he does this quick computation, and figures out that the best knapsack he can take is made up of items 1,3, and 4, for a total value of 29.
  • 11. Knapsack problem There are two versions of the problem: 1. 0-1 knapsack problem Items are indivisible; you either take an item or not. Some special instances can be solved with dynamic programming Exhibit No greedy choice property. No greedy algorithm exists. Exhibit optimal substructure property. Only dynamic programming algorithm exists. .
  • 12. 1. Fractional knapsack problem Items are divisible: you can take any fraction of an item Exhibit greedy choice property. Greedy algorithm exists. Exhibit optimal substructure property
  • 13. 0-1 Knapsack Problem The thief wants to steal n items The ith item weighs wi and has value vi Take the most valuable load, limit of W pounds This is called the 0-1 version of the problem because there are no fractions. The thief must take the whole item or leave it behind.
  • 14. Both the 0-1 Knapsack Problem and the Fractional Knapsack Problem have optimal substructure. If we remove item j from the optimal load, the remaining problem must be optimal for the remaining W - wj pounds for the overall solution to be optimal. The greedy solution for the Fractional Knapsack Problem does not work here
  • 15. Example: Item Value Weight 1 60 10 2 100 20 3 120 30 W = 50 The greedy solution would select 1, leaving 40 pounds. At this point if we pick items 1 and 2 the total value is 160. If we pick items 1 and 3 the total value is 180. The optimal solution is to pick items 2 and 3. The total value of this solution is 220
  • 16. Example: Fractional Knapsack Problem A thief considers taking W pounds of loot. The loot is in the form of n items, each with weight wi and value vi. Any amount of an item can be put in the knapsack as long as the weight limit W is not exceeded.
  • 17. Question: How much of which items should the thief take to maximize the value of the loot? Greedy Algorithm: Take as much of the item with the highest value per pound (vi/wi) as you can. If you run out of that item, take from the next highest (vi/wi) item. Continue until knapsack is full.