Students are very happy when they see some real applications of the theory. Any suggestions for interesting examples of knapsack problems?
$\begingroup$
$\endgroup$
6
-
1$\begingroup$ Guessing that there could be thousands of examples, could you supply some form of constraints, or objectives to the list? Or, at the least, supply information helpful in determining what "interesting" might entail. Stock prices/values might be interesting to an economics major, not so much to a teenage student. $\endgroup$– Gypsy SpellweaverCommented Jan 4, 2020 at 4:32
-
$\begingroup$ They are computer science student and they would be very happy to know they can contribute in any area: science, economy, finance, transportation, engineering, etc. $\endgroup$– Drimades BoyCommented Jan 4, 2020 at 17:47
-
1$\begingroup$ You mean applications other than the knapsack application it is literally named after? I mean, you're basically asking us to Google for you. Wikipedia alone has plenty of examples already. $\endgroup$– FlaterCommented Jan 6, 2020 at 11:37
-
$\begingroup$ I agree this is not worded as a teaching question (just look it up). Unless you ask what are good examples for improving motivation/enguagement in a class of year X (age Y to Z) with W experience. $\endgroup$– ctrl-alt-delorCommented Jan 7, 2020 at 17:44
-
$\begingroup$ I haven't studied it, but it appears to be a cost / benefit scenario, and so anything involving money and products would work. For example, you have 50 dollars to spend on groceries for the week. Given a (fictionally restricted) list of items with calorie values and costs, how can you maximize your calorie intake? You could choose lots of money examples: getting the most rides out of an amusement park, getting the most miles out of a travel budget, or fuel economy choices, etc. In almost any situation money is involved, there are options and tradeoffs, and it can be complex. $\endgroup$– Scott RoweCommented Feb 21, 2020 at 0:27
|
Show 1 more comment
2 Answers
$\begingroup$
$\endgroup$
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.
$\begingroup$
$\endgroup$
-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)
