# Subset sum with only two item types

Suppose we have $$r$$ copies of the integer $$a$$ and $$t$$ copies of the integer $$b$$, and a capacity $$C$$. We would like to find the maximum sum of the given integers, that is at most $$C$$.

This is a special case of the subset sum problem. Since there are at most $$(r+1)(t+1)$$ possible sums, one can just check all of them and find the maximum sum that is at most $$C$$. But this takes time $$O(r t)$$, while the size of the input - if it is given in binary - is $$\log{(r t a b)}$$.

Is there an algorithm that solves the problem in time polynomial in the size of the binary representation of the input?

• There is a simple algorithm in $O(r+t)$, but it still doesn't achieve the bound you wanted. Nov 18, 2021 at 18:23
• There is also a simple algorithm that runs in time $O^*(\min\{r,t\})$, but that's still too slow (here the $O^*$ notation suppresses polynomial factors in the input size). Nov 18, 2021 at 20:34
• The ordinary subset sum problem would have an input size of r log a + t log b for the same problem, and can easily be solved in polynomial time. There are probably many problems in P, NP etc. where special cases can be encoded with much smaller input size and the solution time goes up relative to the input size. Nov 19, 2021 at 10:20
• This appears to be an integer program in two variables; have you considered Lenstra's algorithm for integer programming? Nov 19, 2021 at 12:43