You don't give enough information.

• do the input values fit into 32-bit signed or unsigned data types? This is quite important.
• what set does the solution (x, y) have to belong to? , , or or something else?
• note that it is useful to use LaTeX when talking about maths problems (one of the tutorials). For example (it does also some aligning):

[dollar sign][dollar sign]
\left\{                              % a parenthesis on the left
\begin{array}{rcl}                   % three-column array; columns aligned right, center and left
  v & = & v_{1}x + v_{2}y \\         % first row
    &   & s_{1}x + s_{2}y\ \leq\ s   % second row
\end{array}
\right.                              % we need to "close" this left bracket
[dollar sign][dollar sign]

.

Or in a similar fashion:

More readable, isn't it?

And a side note: I don't know how others think, but I think you should improve on your interpunction (sorry to say, but the writing style like yours usually discourages me from answering).

Now that you have updated the post with additional data, we can start thinking.

Let's say the number of tests given is small. In such applications we call feasible solutions the solutions which satisfy all the constraints (in our case, s₁x + s₂y ≤ s, x ≥ 0 and y ≥ 0). When we draw it on the plane, we will easily see that the feasible solutions are the lattice points inside or on the boundary of the triangle with vertices (0, 0), and . We have to find the feasible solution for which the value v₁x + v₂y is the biggest.

We can use the following trick:

• if , then for each feasible solution (x, y) the inequality follows. Then we can take each possible nonnegative integer x-coordinate (), take the highest point with this coordinate (when we look at the objective function, it'll become obvious why we shouldn't care about lower points) and check if it isn't the best solution. In this case we have time.

• if , we do exactly the same, but with y-coordinates and get time.

• if nothing above follows, then s₁, s₂ are reasonably small (not bigger than ). Let's say that (x, y) is an optimal feasible solution. Now consider two solutions: (x - s₂, y + s₁) and (x + s₂, y - s₁).

• • if value of the first solution (x - s₂, y + s₁) is not worse than (x, y), we may want it not to be feasible. The value is not worse iff v₁(x - s₂) + v₂(y + s₁) ≥ v₁x + v₂y which reduces to v₂s₁ ≥ v₁s₂. Now I leave as a quick excercise proving that the new point won't be feasible iff x < s₂. It means that if v₂s₁ ≥ v₁s₂, then we have to check only the s₂ first x-coordinates using exactly the same method as above. It means we have running time.
• • similarily we consider the solution (x + s₂, y - s₁). It's not worse iff v₂s₁ ≤ v₁s₂ and not feasible iff y < s₁. We conclude that if v₂s₁ ≤ v₁s₂, we need only to check the s₁ first y-coordinates.

In all four cases, we have total running time (if I'm correct).