CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 3 of 3
  1. #1
    Join Date
    Apr 2009
    Posts
    16

    Algorithm - Minimizing Equation - Dynamic Programming/Greedy

    Hi,

    If we are given an equation say 3x + 2y <= 10, we want to find the value of x and y such that
    x + y = maximum and 10 - 3x - 2y is minimized. How can this be done? I am thinking of it as a dynamic programming problem ! but not sure if I am right.

    In the above x = 0 and y = 5 will be the answer.

    Thanks.

  2. #2
    Join Date
    May 2009
    Posts
    2,413

    Re: Algorithm - Minimizing Equation - Dynamic Programming/Greedy

    Quote Originally Posted by vsha041 View Post
    x + y = maximum and 10 - 3x - 2y is minimized. How can this be done?
    I don't know that much about multiple objective optimization but here's a link.

    http://en.wikipedia.org/wiki/Multi-o...e_optimization

    In your particular example though the two objective functions aren't conflicting really so I guess it's a special case. You have this objective,

    Min F2 = 10 - (3x + 2y)

    with the constraint that

    3x + 2y <= 10

    It's easy to see that F2 becomes smaller when (3x + 2y) grows bigger. But (3x + 2y) is limited by 10 so F2 is at minimum when

    3x + 2y = 10

    Then you have this objective

    Max F1 = x + y

    and it's in fact unlimited on

    3x + 2y = 10

    F1 gets forever bigger when x gets smaller.

    If you set say x=-10 then the corresponding y=20. If you enter this into F1 you get F1 = -10 + 20 = 10. Note that this is better than you got with x=0 and y=5 so that really wasn't the optimum.

    All objectives could be met in this case but normally that wouldn't be possible. Then you'd need some way to mathematically express how to weight together all objective functions into one unified objective. According to the link I supplied one answer is "pareto optimization".
    Last edited by nuzzle; September 10th, 2012 at 01:27 AM.

  3. #3
    Join Date
    Apr 2009
    Posts
    16

    Re: Algorithm - Minimizing Equation - Dynamic Programming/Greedy

    Thanks nuzzle for thorough explanation. I actually implemented a greedy algorithm and it worked perfectly. Thanks for your time.

Tags for this Thread

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  





Click Here to Expand Forum to Full Width

Featured