How best we can allocate?

Question

Thank you for this opportunity to share my post here

Advanced thanks to the people who answered my post

Problem: There are $5$ items and cost of these items in dollars are $3$, $3.2$, $4.5$, $2.5$, $1.7$ respectively. How can we allocate $100$ dollars to buy the above items in a such way in order to get maximum number of items in our hand.

1. All types of items should be covered
2. Repetition of items may be allowed
3. Maximum number of items should be purchased
4. Not necessary to spend entire $100$. but, maximum amount should spend near to $100$ or with entire $100$
5. We need to buy each kind of item as much as possible

How to solve this type of problem? Kindly answer Thanks again

Answer 1

Let $n \in \mathbb{N}$ be the amount of dollars to spend, let $a_1, a_2, ..., a_k$ be the objects we want to buy, with prices $p_1, p_2, ..., p_k \in \mathbb{N}$. As we can reorder these items freely, we can assume that their prices are ordered increasingly, that is: $p_1 \leq p_2 \leq ... \leq p_k$.

Define $p = \sum_{i=0}^k p_k$, the total price of all items.

We can write $n = qp + r$, for some $q,r \in \mathbb{N}$ and $0 \leq r < p$. This is equivalent to dividing $n$ by $p$ with rest. As we want to buy all items an almost equal amount, we therefore by $q$ sets of all items, and then have $r$ dollars left over.

With these $r$ dollars, we can buy the items $p_1, p_2, ..., p_k$, until we run out of dollars. We always buy the least expensive item first, so we have as much cash left over as possible. In this case, the question becomes (and I don't think there is a simple formula for this):

What is the largest value of $j\in\mathbb{N}$, such that $r > \sum_{i=0}^j p_i$.

This value of $j$ is the amount of items we can buy with the remaining $r$ dollars.

Putting al this together: We can buy $q$ sets of $k$ items, and with the remaining $r$ dollars we can buy $j$ items, so in in total we can buy $qk+j$ items with our $n$ dollars.

Answer 2

You can solve the problem via integer linear programming as follows. For item $i$, let $c_i$ be the cost, and let integer decision variable $x_i$ be the number bought. The problem is to maximize $\sum_i x_i$ subject to \begin{align} \sum_i c_i x_i &\le 100 \\ x_i &\ge 1 &&\text{for all $i$} \end{align} An optimal solution is $x=(1,1,1,1,51)$, with optimal objective value $55$.

If you want the numbers of items bought to vary by no more than $1$, you can impose additional constraint $$-1 \le x_i - x_j \le 1 \quad \text{for all $i<j$}.$$ An optimal solution is $x=(7,7,6,7,7)$, with optimal objective value $34$.