# Given a set of integers $D$ and a positive value$P$, find an algorithm to find set of integers satisfying a condition

Given a set of positive integers :

$$\\ D = \{ D_1, D_2, ..., D_n\}$$

and a non-negative integer $$P$$, where $$P$$ is divisible by every element in $$D$$, then find a set of non-negative integers:

$$C = \{ C_1, C_2,..., C_n\}$$

such that

$$S > P$$

where
$$S = \displaystyle \sum_{i = 1}^nC_iD_i$$
and for all $$i$$ where $$C_i > 0$$,

$$\ S - D_i < P$$

There can be multiple solutions, any solution can suffice.

For example, if

$$D = \{2, 6, 9 \}$$
$$P = 18$$

$$C$$ can be:

$$C = \{0, 2, 1 \}$$

since $$S = 0*2 + 2*6 + 1*9 = 21 > 18$$
and $$21 - 6 = 15 < 18$$ and $$21 - 9 = 12 < 18$$

What can be some approaches to tackle this? For starters, is there a way to ensure that there even exists a solution? There can be examples where there is no solution.

• What approaches have you considered? What progress have you made so far?
– D.W.
Commented Feb 14, 2020 at 0:46
• @D.W. I have tried approaching it by finding 2 integers Ci and Cj such that the condition is satisfied. The result gives that if there are Di and Dj such that Di < Dj and 2*Di > Dj, then we can have Ci = P/Di - 1 and Cj = 1 rest all zero. Commented Feb 14, 2020 at 14:58
• Thanks for the edits, I find that a lot clearer. I suggest you start by trying to solve the special case $n=2$ first. Can you do that? What's the context where you encountered this? Can you credit the source where you originally saw it?
– D.W.
Commented Feb 14, 2020 at 15:31

If all of $$D$$ divide $$P$$, then $$P$$ is also multiple of $$\gcd(D)$$. Any sum like $$S$$ is a multiple of $$\gcd(D)$$ too, so you can divide everything by $$\gcd(D)$$ and consider just the case where the $$D_i$$ are relatively prime. For definiteness, take $$D$$ sorted in increasing order. In that case you have just:
$$\begin{equation*} P = c \cdot \prod_{1 \le k \le n} D_k \end{equation*}$$
For the Frobenius problem sums like $$S$$ with non-negative $$C_i$$ can represent all numbers greater than a function $$g(D)$$, and it can be shown that $$g(D) < D_n^2$$ (computing the exact value of $$g(D)$$ is NP-complete). So, if $$P > D_n^2$$ (the other $$D_k$$ would have to be small indeed for this to be false), any number $$S \ge P$$ can be represented, and also any number $$S - D_i$$, pick say $$S = P + 1$$ to satisfy your condition.
To get a set of $$C_i$$, you can now use the greedy algorithm: Take $$C_n = \lfloor S / D_n \rfloor$$ (as large as possible), $$S \leftarrow S - C_n D_n$$, and repeat for the next largest.