Thinking if it is a Knapsack problem.

Here is the scenario:

Michael and his daughter (7 year old kid) enjoy going to cinema for movies.

Weekdays fare for kids is 5 dollars, adult 8.
Weekend fare $12.00, regardless kid or adult.

With $100 budget, how can Michael and his daughter enjoy more movies, considering most of those falls in weekdays?


So it costs \$13 for the two of them on a weekday and \$24 for the two of them on a weekend. If you want to maximize the number of movies, skip the expensive ones and the \$100 budget yields $\lfloor 100/13 \rfloor = 7$ movies.

If you prefer writing it explicitly as an optimization (yes, knapsack) problem, let integer decision variables $x$ and $y$ be the numbers of weekday and weekend movies attended, respectively. The problem is to maximize $x+y$ subject to linear constraints \begin{align} 13x+24y &\le 100 \\ x &\ge 0 \\ y &\ge 0 \end{align} The unique optimal solution is $(x,y)=(7,0)$, with objective value $7+0=7$.

  • 1
    $\begingroup$ thank you for the guidance! that's fantastic! $\endgroup$ – Mark K Dec 31 '20 at 6:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.