Does there exist a way to efficiently solve the following problem?
Given some constant $k$ and several sets of non-negative integers:
$a_0\in\{a_{0,0},a_{0,1},...,a_{0,m_0}\},$
$a_1\in\{a_{1,0},a_{1,1},...,a_{1,m_1}\},$
$ ...,$
$ a_n\in\{a_{n,0},a_{n,1},...,a_{n,m_n}\}$
$\forall i \forall j, 0 \leq a_{i,j} < k$
Find the smallest sum $S = a_0+a_1+...+a_n$ such that $S \geq k$.
I know that the problem is trivial when $k = 0$, but am unsure if there exists an efficient approach when $k > 0$.
This is NP complete even in the special case where each set has two elements one of which is $0.$ This can be shown by a reduction to exact cover : Given a family $\mathcal{S}$ of subsets of a set $X,$ is there a subfamily $\mathcal{S}^*$ using each element of $X$ exactly once?
For the reduction, let the set $X$ be $\{{0,1,2,\cdots,N-1\}}$ and the family $\mathcal{S}$ have less than $b$ members. Replace each set $A \in \mathcal{S}$ by $\{{0,a\}}$ where $a=\sum_{i \in A}b^i$, in other words, the number which, in base $b$, is a $0,1$ string with a $1$ to indicate each element of $A$. Then take as the target sum $k=\frac{b^{N}-1}{b-1}=\sum_0^{N-1}b^i=111\cdots1_b.$ The choice of the base $b$ insures that carrying is not relevant. So if the minimum sum greater than or equal to $k$ is exactly $k$, then there is an exact cover of $X$ by a subfamily of $\mathcal{S}$. Otherwise, there is not.
Note: There is a brilliantly efficient algorithm Dancing Links to find all solutions to an instance of exact cover. The problem is still NP complete however if you have to try to find a solution in a particular case, there is a good way to go at it. However that is only a very special case of your problem.
