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


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

for i = a to t
   m[i] = m[i - a] OR m[i - b] OR m[i - c]
   if m[i] = F
      w = i
return w

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.

| cite | improve this answer | |

You can easily sovle this problem with dynprog, if it is nessesary. It is $O(t)$. There are for sure much better algorithms, but your question has a tag "dynamic-programming"... http://pastebin.com/QN2BJL17

| cite | improve this answer | |

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.