Students are very happy when they see some real applications of the theory. Any suggestions for interesting examples of knapsack problems?
I'll probably try with this one, from an actual software I almost developed.
- There's a factory that produces paints in various colours.
- The factory has a single production line that can produce only one colour in a given moment. It's capacity is also limited, i.e. 1000 litres per day regardless of the colour produced.
- Different colours have different production costs and are sold at different prices. I.e.: white is cheap to produce and is selling price is low. Gold is expensive to produce because metal sand has to be added in the paint to give it a shiny note. Gold is also sold at higher price. Red lies in between.
- Different customer requires different amount of paint, i.e.: customer A asks for 1000 litres of white, customer B and customer C asks for 250 litres of gold each, customer D for 700 litres of red.
That given, the problem is to find the mix of production that maximise the profit.
-Tim Roughgarden gives an example of selecting TV advertisements for a fixed time interval, different price for different kinds of goods advertised, and of course different duration for each ad. (called Knapsack auctions) https://youtu.be/BMoSLmuJsak
-I think there r examples on utilizing networks fixed B.W., not very sure of the details.
-Then, in these days with COVID-19 nothing wrong with the classic super market bag example (u want to store as useful goods as u can carry, with all deals & discounts they r offering u). Even without coronavirus, there is an MIT prof. that uses the supermarket example in his AI lectures.
https://youtu.be/leXa7EKUPFk (hope it's this exact lecture)