I'm trying to figure out this problem for few hours now. please help.
Define $$\text{PCOM}(a,b,c) := \{ax + by + cz : x, y, z ≥ 0\}.$$
Given integers $t > c > b > a > 1,$ I need help to find the largest integer $w < t$ such that $w\notin\text{PCOM}(a,b,c).$
Example: $\text{PCOM}(3,5,7) =\{0,3,5,6,7,8,9,10,…\}.$ The largest integer less than $9$ that is not in $\text{PCOM}(3,5,7)$ is $4$.
Best Answer
This is a particularly simple variant of what is known as the coin problem. Here's a dynamic programming solution that runs in time linear in $t$. We use an array $m[0\dots t]$ of booleans, which I'll refer to as either T or F. The value of $m[i]$ will represent whether or not $i$ can be represented as the sum of zero or more copies of $a, b, c$. We will also keep a variable $w$, representing the current largest value not in $\text{PCOM}(a, b, c)$.
First, we initialize $m[0] = \text{T}$ (since we can obviously get a sum of zero by not using any of the values) and for $0 < i < a$ we set $m[i]=\text{F}$. We also initialize $w=a-1$.
Having done that, the algorithm is
The only tweak is in the second line: if $i < b$ or $i < c$ we don't try to access the corresponding array element (since it would make no sense to do so here). There are some obvious improvements we can make in the algorithm, but I hope the idea is clear. If not, just ask.