# Linear Program Modelling Coinset pay amount $k$

You are given a coinset ov values c1,...,cn and a target value of k you need to pay. For each i element {1,...,n} let ni be the number of coins of value ci in your wallet. You want to pay (or overpay) the target value k such that the number of coins in your wallet (after the change has been paid) is minimized. You can assume that the change is returned in a minimum number of coins. Contrusct an ILP that sloves the problem. Explain the meaning of all the variables.

I have no glue.... Here is my "try":

Variable: x - for the number of coins in my wallet (coinset c1,...,n) c - the value of the Sum of the Coins

Objective Function:

      min the Sum of the coins in my wallet: also min x


Constraints:

      s.t.      c <= k


I think this is not complete and not right......

• Are the coins $c_1, \dots, c_n$ all the coins that exist in this "universe"? If not, we have incomplete information to solve the problem. – 79037662 Sep 19 '19 at 14:16
• Also the variable $n$ is being used for both the number of coin types and the number of each coin you have. – 79037662 Sep 19 '19 at 14:16

First of all, the question uses the variable $$n$$ to represent both the number of coin types and the number of each coin you have. This is confusing to say the least, so let's say you have $$m_i$$ coins of value $$c_i$$ to begin with, where $$i$$ ranges from $$1, \dots, n$$. Secondly, I'm assuming one can neglect the change returned; the question is unclear in this regard.

Instead of having one variable $$x$$ representing the total amount, let's have variables $$x_1, \dots, x_n$$ where $$x_i$$ is the number of coins of value $$c_i$$ that you spend. Therefore, your objective function is the following:

$$\min m_1 + \dots + m_n - x_1 - \dots - x_n$$

Now, consider the constraints. We need the value of the coins we spend to equal or exceed $$k$$:

$$c_1x_1+\dots+c_nx_n\geq k$$

We cannot spend more coins than we have:

$$x_1\leq m_1$$

$$\vdots$$

$$x_n\leq m_n$$

We must spend a nonnegative number of coins:

$$x_1\geq0$$

$$\vdots$$

$$x_n\geq0$$

Finally, all variables are integers:

$$x_1, \dots, x_n\text{ integer}$$