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 


      s.t.      c <= k

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

  • $\begingroup$ 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. $\endgroup$ – 79037662 Sep 19 '19 at 14:16
  • $\begingroup$ Also the variable $n$ is being used for both the number of coin types and the number of each coin you have. $\endgroup$ – 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$$


$$x_n\leq m_n$$

We must spend a nonnegative number of coins:




Finally, all variables are integers:

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


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.