<p>I'll probably try with this one, from an actual software I almost developed.</p>

<ul>
<li>There's a factory that produces paints in various colours. </li>
<li>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.</li>
<li>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. </li>
<li>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.</li>
</ul>

<p>That given, the problem is to find the mix of production that maximise the profit.</p>

CC BY-SA 4.0
2020-05-01T01:09:08.303Z
2020-05-01T01:09:08.303Z
danidemi
<p>-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) 
<a href="https://youtu.be/BMoSLmuJsak" rel="nofollow noreferrer">https://youtu.be/BMoSLmuJsak</a></p>

<p>-I think there r examples on utilizing networks fixed B.W., not very sure of the details. </p>

<p>-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 &amp; discounts they r offering u). Even without coronavirus, there is an MIT prof. that uses the supermarket example in his AI lectures.    </p>

<p><a href="https://youtu.be/leXa7EKUPFk" rel="nofollow noreferrer">https://youtu.be/leXa7EKUPFk</a> (hope it's this exact lecture) </p>

CC BY-SA 4.0
2020-05-12T07:58:28.900Z
2020-05-12T07:58:28.900Z
ShAr
<p>Students are very happy when they see some real applications of the theory. Any suggestions for interesting examples of knapsack problems?</p>

CC BY-SA 4.0
2020-01-04T04:32:16.553Z
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.
Gypsy Spellweaver
CC BY-SA 4.0
2020-01-04T17:47:38.067Z
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.
Drimades Boy
CC BY-SA 4.0
2020-01-06T11:37:59.613Z
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.
Flater
CC BY-SA 4.0
2020-01-07T17:44:27.007Z
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.
ctrl-alt-delor
CC BY-SA 4.0
2020-02-21T00:27:22.750Z
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.
Scott Rowe
CC BY-SA 4.0
2020-03-10T14:41:01.230Z
Just came across this article while browsing Hacker News today: https://www.smithsonianmag.com/science-nature/why-knapsack-problem-all-around-us-180974333/ "How the Mathematical Conundrum Called the ‘Knapsack Problem’ Is All Around Us"
Kurt Schwanda
<teaching-analogy><algorithms>
What are some real life applications of the knapsack problems class?
# What are some real life applications of the knapsack problems class?

(Asked by: username_0 on 2020-01-04)

Students are very happy when they see some real applications of the theory. Any suggestions for interesting examples of knapsack problems?

**Tags:** teaching-analogy, algorithms

> **Comments:**
> **username_1**: 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.  
> **username_0**: 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.  
> **username_2**: 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.  
> **username_3**: 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.  
> **username_4**: 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.  
> **username_5**: Just came across this article while browsing Hacker News today: https://www.smithsonianmag.com/science-nature/why-knapsack-problem-all-around-us-180974333/ "How the Mathematical Conundrum Called the ‘Knapsack Problem’ Is All Around Us"  

---

## 2 answers

### Answer by username_6 on 2020-05-01. Score: 3

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.


---

### Answer by username_7 on 2020-05-12. Score: 2

-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)


---

