DISCRETE MATH The \"Knapsack\" Problem A hiker has a number of items that he wou
ID: 3774349 • Letter: D
Question
DISCRETE MATH The "Knapsack" Problem A hiker has a number of items that he would like to take with him on his next trip. Unfortunately, not all of the items can fit in his knapsack, so he would have to select the items that have the most "value" to him, and leave the remaining items at home. He can build a chart with the following form to help him: ItemValueSize (Volume) Lantern 15 250 Frying pan 12 100 Knife 10 20 Radio 20 400 In this simple case, we assume that the decisions for the items are "mutually independent". That is, deciding to include or exclude some item from the knapsack does not affect the relative value of some other item. The objective for the hiker is to find out which items to bring in order to maximize the total value. In an integer programming formulation of the situation, we let n represent the number of items available, numbered 1, 2, ... n. We let B represent the capacity of the knapsack. For item k, we let ck represent the value of the item and let ak represent the size of the item. The objective is to: Maximixe V = c1 x1 + c2 x2 + c3 x3 +...+ cn xn subject to: a1 x1 + a2 x2 + a3 x3 +...+ an xn £ B 0 £ xi £ 1 and integer The variable xi is set to 1 if item i is included and to 0 if it is excluded. The inequality is often referred to as a “budget constraint” because total space is limited. Note that you cannot put the same item in more than once. In an enumerative approach, you solve the problem of finding the set of items with the highest total value, i.e., find the “optimal set”, by identifying every subset of items. We remove from consideration those subsets that exceed the budget limit. Then, we select from the remaining (feasible) subsets to identify one having the largest total value. Many solution approaches involve some form of smart enumeration to cut down on the total amount of work (computational effort) required to find the optimal set. In a dynamic programming approach, the problem is solved using recursion. We point out that the optimal set will either contain the last item, item n, or it will not. If it doesn’t, then the optimal set is found by solving the problem with a knapsack of size B over the remaining items 1…n-1. An astute observer would recognize that if an optimal set includes item n, then the optimal set has that item plus the optimal choices among the other items 1…n-1 that would fit into the remaining space which is equivalent to a knapsack of size B-an. Let V(k, S) be a function that represents the optimal total value that could be obtain from by solving the problem by considering only items 1…k and having a sack of size S. Then the optimal value of our Knapsack Problem is V(n, B), which equals: Max(V(n-1, B), cn + V(n-1, B-an)) That is, the optimal value is the larger of the potential optimal value without item n and the potential optimal value without item n. In general the recursive equation is: V(k, S) = Max(V(k-1, s), ck + V(k-1, B-ak)). To solve the recursion we consider the following initial conditions for the function: • V(k, 0) must equal 0 for all k, because a knapsack of size 0 can’t hold any items. • V(k, S) is - when S<0 because there is no such thing as a knapsack with negative capacity. • V(1, S) must equal 0 if S < a1 because the only item to consider doesn’t fit in the knapsack and V(1, S) must be equal to c1 when S a1 because there is only one item to consider and it fits. Thus, it is possible to solve the problem by populating a two-dimensional array (matrix) for V of size (B+1)×n with these initial values and then using the recursion equation to populate additional locations until a value is found for V(n, B). You should keep track of whether the optimal solution for V(n, B) included item n or not. Then you can backtrack to find out whether item n-1 is included and so on until you know whether item 1 is included. Exercises 1. Consider the following instance of the Knapsack Problem with n=7 and B=10: Item #1234567 Size3452365 Value4781649 a) Use some enumerative approach to find the optimal set. b) Find the optimal value using the Dynamic Programming approach. Show your backtracking to find which items to put into the knapsack. 2. Prove the following: If S < T then V(n, S) V(n, T) 3. Prove the following: If n < m then V(n, S) V(m, S) Extra Credit: Suppose you were allowed to place as many as two of any item into the knapsack. Can you do this without changing your solution algorithm? If so, provide the optimal set for this case. Extra Credit: Describe some ways to make your algorithm more efficient, e.g., so that you don’t have to fill in the entire matrix to find V(n, B). Extra Credit: If you wish, you and some others in a group may write a computer program to solve the Knapsack Problem. You would have to demonstrate that it works in person. DISCRETE MATH The "Knapsack" Problem A hiker has a number of items that he would like to take with him on his next trip. Unfortunately, not all of the items can fit in his knapsack, so he would have to select the items that have the most "value" to him, and leave the remaining items at home. He can build a chart with the following form to help him: ItemValueSize (Volume) Lantern 15 250 Frying pan 12 100 Knife 10 20 Radio 20 400 In this simple case, we assume that the decisions for the items are "mutually independent". That is, deciding to include or exclude some item from the knapsack does not affect the relative value of some other item. The objective for the hiker is to find out which items to bring in order to maximize the total value. In an integer programming formulation of the situation, we let n represent the number of items available, numbered 1, 2, ... n. We let B represent the capacity of the knapsack. For item k, we let ck represent the value of the item and let ak represent the size of the item. The objective is to: Maximixe V = c1 x1 + c2 x2 + c3 x3 +...+ cn xn subject to: a1 x1 + a2 x2 + a3 x3 +...+ an xn £ B 0 £ xi £ 1 and integer The variable xi is set to 1 if item i is included and to 0 if it is excluded. The inequality is often referred to as a “budget constraint” because total space is limited. Note that you cannot put the same item in more than once. In an enumerative approach, you solve the problem of finding the set of items with the highest total value, i.e., find the “optimal set”, by identifying every subset of items. We remove from consideration those subsets that exceed the budget limit. Then, we select from the remaining (feasible) subsets to identify one having the largest total value. Many solution approaches involve some form of smart enumeration to cut down on the total amount of work (computational effort) required to find the optimal set. In a dynamic programming approach, the problem is solved using recursion. We point out that the optimal set will either contain the last item, item n, or it will not. If it doesn’t, then the optimal set is found by solving the problem with a knapsack of size B over the remaining items 1…n-1. An astute observer would recognize that if an optimal set includes item n, then the optimal set has that item plus the optimal choices among the other items 1…n-1 that would fit into the remaining space which is equivalent to a knapsack of size B-an. Let V(k, S) be a function that represents the optimal total value that could be obtain from by solving the problem by considering only items 1…k and having a sack of size S. Then the optimal value of our Knapsack Problem is V(n, B), which equals: Max(V(n-1, B), cn + V(n-1, B-an)) That is, the optimal value is the larger of the potential optimal value without item n and the potential optimal value without item n. In general the recursive equation is: V(k, S) = Max(V(k-1, s), ck + V(k-1, B-ak)). To solve the recursion we consider the following initial conditions for the function: • V(k, 0) must equal 0 for all k, because a knapsack of size 0 can’t hold any items. • V(k, S) is - when S<0 because there is no such thing as a knapsack with negative capacity. • V(1, S) must equal 0 if S < a1 because the only item to consider doesn’t fit in the knapsack and V(1, S) must be equal to c1 when S a1 because there is only one item to consider and it fits. Thus, it is possible to solve the problem by populating a two-dimensional array (matrix) for V of size (B+1)×n with these initial values and then using the recursion equation to populate additional locations until a value is found for V(n, B). You should keep track of whether the optimal solution for V(n, B) included item n or not. Then you can backtrack to find out whether item n-1 is included and so on until you know whether item 1 is included. Exercises 1. Consider the following instance of the Knapsack Problem with n=7 and B=10: Item #1234567 Size3452365 Value4781649 a) Use some enumerative approach to find the optimal set. b) Find the optimal value using the Dynamic Programming approach. Show your backtracking to find which items to put into the knapsack. 2. Prove the following: If S < T then V(n, S) V(n, T) 3. Prove the following: If n < m then V(n, S) V(m, S) Extra Credit: Suppose you were allowed to place as many as two of any item into the knapsack. Can you do this without changing your solution algorithm? If so, provide the optimal set for this case. Extra Credit: Describe some ways to make your algorithm more efficient, e.g., so that you don’t have to fill in the entire matrix to find V(n, B). Extra Credit: If you wish, you and some others in a group may write a computer program to solve the Knapsack Problem. You would have to demonstrate that it works in person. DISCRETE MATH The "Knapsack" Problem A hiker has a number of items that he would like to take with him on his next trip. Unfortunately, not all of the items can fit in his knapsack, so he would have to select the items that have the most "value" to him, and leave the remaining items at home. He can build a chart with the following form to help him: ItemValueSize (Volume) Lantern 15 250 Frying pan 12 100 Knife 10 20 Radio 20 400 In this simple case, we assume that the decisions for the items are "mutually independent". That is, deciding to include or exclude some item from the knapsack does not affect the relative value of some other item. The objective for the hiker is to find out which items to bring in order to maximize the total value. In an integer programming formulation of the situation, we let n represent the number of items available, numbered 1, 2, ... n. We let B represent the capacity of the knapsack. For item k, we let ck represent the value of the item and let ak represent the size of the item. The objective is to: Maximixe V = c1 x1 + c2 x2 + c3 x3 +...+ cn xn subject to: a1 x1 + a2 x2 + a3 x3 +...+ an xn £ B 0 £ xi £ 1 and integer The variable xi is set to 1 if item i is included and to 0 if it is excluded. The inequality is often referred to as a “budget constraint” because total space is limited. Note that you cannot put the same item in more than once. In an enumerative approach, you solve the problem of finding the set of items with the highest total value, i.e., find the “optimal set”, by identifying every subset of items. We remove from consideration those subsets that exceed the budget limit. Then, we select from the remaining (feasible) subsets to identify one having the largest total value. Many solution approaches involve some form of smart enumeration to cut down on the total amount of work (computational effort) required to find the optimal set. In a dynamic programming approach, the problem is solved using recursion. We point out that the optimal set will either contain the last item, item n, or it will not. If it doesn’t, then the optimal set is found by solving the problem with a knapsack of size B over the remaining items 1…n-1. An astute observer would recognize that if an optimal set includes item n, then the optimal set has that item plus the optimal choices among the other items 1…n-1 that would fit into the remaining space which is equivalent to a knapsack of size B-an. Let V(k, S) be a function that represents the optimal total value that could be obtain from by solving the problem by considering only items 1…k and having a sack of size S. Then the optimal value of our Knapsack Problem is V(n, B), which equals: Max(V(n-1, B), cn + V(n-1, B-an)) That is, the optimal value is the larger of the potential optimal value without item n and the potential optimal value without item n. In general the recursive equation is: V(k, S) = Max(V(k-1, s), ck + V(k-1, B-ak)). To solve the recursion we consider the following initial conditions for the function: • V(k, 0) must equal 0 for all k, because a knapsack of size 0 can’t hold any items. • V(k, S) is - when S<0 because there is no such thing as a knapsack with negative capacity. • V(1, S) must equal 0 if S < a1 because the only item to consider doesn’t fit in the knapsack and V(1, S) must be equal to c1 when S a1 because there is only one item to consider and it fits. Thus, it is possible to solve the problem by populating a two-dimensional array (matrix) for V of size (B+1)×n with these initial values and then using the recursion equation to populate additional locations until a value is found for V(n, B). You should keep track of whether the optimal solution for V(n, B) included item n or not. Then you can backtrack to find out whether item n-1 is included and so on until you know whether item 1 is included. Exercises 1. Consider the following instance of the Knapsack Problem with n=7 and B=10: Item #1234567 Size3452365 Value4781649 a) Use some enumerative approach to find the optimal set. b) Find the optimal value using the Dynamic Programming approach. Show your backtracking to find which items to put into the knapsack. 2. Prove the following: If S < T then V(n, S) V(n, T) 3. Prove the following: If n < m then V(n, S) V(m, S) Extra Credit: Suppose you were allowed to place as many as two of any item into the knapsack. Can you do this without changing your solution algorithm? If so, provide the optimal set for this case. Extra Credit: Describe some ways to make your algorithm more efficient, e.g., so that you don’t have to fill in the entire matrix to find V(n, B). Extra Credit: If you wish, you and some others in a group may write a computer program to solve the Knapsack Problem. You would have to demonstrate that it works in person. DISCRETE MATH The "Knapsack" Problem A hiker has a number of items that he would like to take with him on his next trip. Unfortunately, not all of the items can fit in his knapsack, so he would have to select the items that have the most "value" to him, and leave the remaining items at home. He can build a chart with the following form to help him: ItemValueSize (Volume) Lantern 15 250 Frying pan 12 100 Knife 10 20 Radio 20 400 In this simple case, we assume that the decisions for the items are "mutually independent". That is, deciding to include or exclude some item from the knapsack does not affect the relative value of some other item. The objective for the hiker is to find out which items to bring in order to maximize the total value. In an integer programming formulation of the situation, we let n represent the number of items available, numbered 1, 2, ... n. We let B represent the capacity of the knapsack. For item k, we let ck represent the value of the item and let ak represent the size of the item. The objective is to: Maximixe V = c1 x1 + c2 x2 + c3 x3 +...+ cn xn subject to: a1 x1 + a2 x2 + a3 x3 +...+ an xn £ B 0 £ xi £ 1 and integer The variable xi is set to 1 if item i is included and to 0 if it is excluded. The inequality is often referred to as a “budget constraint” because total space is limited. Note that you cannot put the same item in more than once. In an enumerative approach, you solve the problem of finding the set of items with the highest total value, i.e., find the “optimal set”, by identifying every subset of items. We remove from consideration those subsets that exceed the budget limit. Then, we select from the remaining (feasible) subsets to identify one having the largest total value. Many solution approaches involve some form of smart enumeration to cut down on the total amount of work (computational effort) required to find the optimal set. In a dynamic programming approach, the problem is solved using recursion. We point out that the optimal set will either contain the last item, item n, or it will not. If it doesn’t, then the optimal set is found by solving the problem with a knapsack of size B over the remaining items 1…n-1. An astute observer would recognize that if an optimal set includes item n, then the optimal set has that item plus the optimal choices among the other items 1…n-1 that would fit into the remaining space which is equivalent to a knapsack of size B-an. Let V(k, S) be a function that represents the optimal total value that could be obtain from by solving the problem by considering only items 1…k and having a sack of size S. Then the optimal value of our Knapsack Problem is V(n, B), which equals: Max(V(n-1, B), cn + V(n-1, B-an)) That is, the optimal value is the larger of the potential optimal value without item n and the potential optimal value without item n. In general the recursive equation is: V(k, S) = Max(V(k-1, s), ck + V(k-1, B-ak)). To solve the recursion we consider the following initial conditions for the function: • V(k, 0) must equal 0 for all k, because a knapsack of size 0 can’t hold any items. • V(k, S) is - when S<0 because there is no such thing as a knapsack with negative capacity. • V(1, S) must equal 0 if S < a1 because the only item to consider doesn’t fit in the knapsack and V(1, S) must be equal to c1 when S a1 because there is only one item to consider and it fits. Thus, it is possible to solve the problem by populating a two-dimensional array (matrix) for V of size (B+1)×n with these initial values and then using the recursion equation to populate additional locations until a value is found for V(n, B). You should keep track of whether the optimal solution for V(n, B) included item n or not. Then you can backtrack to find out whether item n-1 is included and so on until you know whether item 1 is included. Exercises 1. Consider the following instance of the Knapsack Problem with n=7 and B=10: Item #1234567 Size3452365 Value4781649 a) Use some enumerative approach to find the optimal set. b) Find the optimal value using the Dynamic Programming approach. Show your backtracking to find which items to put into the knapsack. 2. Prove the following: If S < T then V(n, S) V(n, T) 3. Prove the following: If n < m then V(n, S) V(m, S) Extra Credit: Suppose you were allowed to place as many as two of any item into the knapsack. Can you do this without changing your solution algorithm? If so, provide the optimal set for this case. Extra Credit: Describe some ways to make your algorithm more efficient, e.g., so that you don’t have to fill in the entire matrix to find V(n, B). Extra Credit: If you wish, you and some others in a group may write a computer program to solve the Knapsack Problem. You would have to demonstrate that it works in person.Explanation / Answer
1)
a)
Enumerative problem solution
maximum values we can get 17
Susbet is 1 2 5
b)
Maximum value is 17
subset is 5 2 1
2)
Proving is quite easy. If you increase the basket size, it means B here then we not only can accomodate those previous items we did but we might accomodate new one or we can choose some other item whose value is more than some either item we had in basket. Suppose new B is 12 then instead of choosing 1 2 and 5 , we chose 2, 3, 6 which will give us now 22 value.
3) Same here if we increase n and add some 1 size item with bigger value it might increase our value.
4) You can add same item twice just in else condition use 3 statement it means,
and increase the includeItem[] where we are storing path.
Remember for accessing size and value array item i have to do k - 1 as i have used 0 indexing. you can either do this or add 0 in 0th index in size and value array
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.