2. Another common problem that is used to design supply chain and warehouse systems is the knapsack or backpack problem. The name comes from an (abstract to be sure) backpacker's dilemma of deciding which items to pack in their knapsack. The person has limited capacity in their backpack and a variety of items from which to pack, each with a unique value and size. Their goal is to maximize the value but not exceed the sack's capacity. Now, when the items are continuous i.e., you can pack 1.0 or 1.1 or 1.12 or 1.034 or whatever fraction of an item) the optimal solution turns out to be easy. We call it a greedy algorithm" because all you do is find the item that has the highest ratio of value to volume and fill the sack with that one item. When the items are discrete (i.e., you can only place one or two or three, etc.) the problem is more complicated and requires a technique like dynamic programming to solve. The following problem is a discrete knapsack problem. The manager of a nationwide trucking company has six newly acquired trucks which she wishes to assign to three large cities (A, B, and C). From historical data, she has determined the incremental profitability of increasing the fleet size in each of the three cities as shown in table below. For example, if she assigns two additional vehicles to city B, profits will increase by $45K. Use dynamic programming to find the allocation of the new trucks to the three cities that maximizes increased profit. As before, carefully define stage, state, and decision variable. Net additional profit from additional truck allocations. (in thousands of dollars) Trucks Allocated City A City B City C 0 1 23 20 38 0 0 0 30 50 2 3 45 60 59 Hint: One way to view this problem that I think makes is a bit easier to see the dynamic programming structure goes like this. Let the stage be the cities and the state be the number of trucks left to assign. Suppose we work through the cities C, B, and A. The first stage would have, in words, three parts: I have only city Cleft in which to allocate trucks and I have 1 truck left to allocate - my decision is allocate 1 truck for a profit of $30K. I have only city Cleft and I have 2 trucks left to allocate - my decision is allocate 2 trucks for a profit of $38K. I have only city Cleft and I have 3 or more trucks left to allocate my decision is allocate 3 trucks for a profit of $59K. Now, translate that into a recursive equation and work is backwards. Next stage is cities B and C to allocate trucks and you work through having between 0 and 6 left to allocate. Final state is A, B and C- and 6 trucks. 2. Another common problem that is used to design supply chain and warehouse systems is the knapsack or backpack problem. The name comes from an (abstract to be sure) backpacker's dilemma of deciding which items to pack in their knapsack. The person has limited capacity in their backpack and a variety of items from which to pack, each with a unique value and size. Their goal is to maximize the value but not exceed the sack's capacity. Now, when the items are continuous i.e., you can pack 1.0 or 1.1 or 1.12 or 1.034 or whatever fraction of an item) the optimal solution turns out to be easy. We call it a greedy algorithm" because all you do is find the item that has the highest ratio of value to volume and fill the sack with that one item. When the items are discrete (i.e., you can only place one or two or three, etc.) the problem is more complicated and requires a technique like dynamic programming to solve. The following problem is a discrete knapsack problem. The manager of a nationwide trucking company has six newly acquired trucks which she wishes to assign to three large cities (A, B, and C). From historical data, she has determined the incremental profitability of increasing the fleet size in each of the three cities as shown in table below. For example, if she assigns two additional vehicles to city B, profits will increase by $45K. Use dynamic programming to find the allocation of the new trucks to the three cities that maximizes increased profit. As before, carefully define stage, state, and decision variable. Net additional profit from additional truck allocations. (in thousands of dollars) Trucks Allocated City A City B City C 0 1 23 20 38 0 0 0 30 50 2 3 45 60 59 Hint: One way to view this problem that I think makes is a bit easier to see the dynamic programming structure goes like this. Let the stage be the cities and the state be the number of trucks left to assign. Suppose we work through the cities C, B, and A. The first stage would have, in words, three parts: I have only city Cleft in which to allocate trucks and I have 1 truck left to allocate - my decision is allocate 1 truck for a profit of $30K. I have only city Cleft and I have 2 trucks left to allocate - my decision is allocate 2 trucks for a profit of $38K. I have only city Cleft and I have 3 or more trucks left to allocate my decision is allocate 3 trucks for a profit of $59K. Now, translate that into a recursive equation and work is backwards. Next stage is cities B and C to allocate trucks and you work through having between 0 and 6 left to allocate. Final state is A, B and C- and 6 trucks