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......
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}$$