selfcompiler's blog

Math Problem
By selfcompiler, 10 years ago, In English

Actually This is a piece of question ,i am struggling in that part so i want help . 1. so the problem is you have two equations — v=x*v1+y*v2
— x*s1+y*s2<=s

you have the values of v1,v2,s1,s2,s all are fit in 32 bit integer .you have to maximize the value of v ?? Constraints : s1>=1,s2>=1,v1>=1,v2>=1,v>=1,s>=1,x>=0,y>=0 and s1,s2,v1,v2,x,y,v,s all are positive integer.

  • Vote: I like it
  • -8
  • Vote: I do not like it

»
10 years ago, # |
  Vote: I like it +13 Vote: I do not like it

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

→ Reply
»
10 years ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

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, s1x + s2y ≤ 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 v1x + v2y 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 s1, s2 are reasonably small (not bigger than ). Let's say that (x, y) is an optimal feasible solution. Now consider two solutions: (x - s2, y + s1) and (x + s2, y - s1).

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

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

→ Reply