2014年4月14日 星期一

Bézout's identity

3x+5y=11, x,yZ, look for (x,y) maximize (x+y)  under the condition: max(x+y)<= 100


#include<iostream>
using namespace std;
int main(){
 int a,b,c;
 cin>>a;
 cin>>b;
 cin>>c;
 int sum=0;
 for(int x=-1000;x<101;x++){

  int x1=x;
  int x2=(-1)*x;
  int y1=(c-a*x1)/b;
  int y2=(c-a*x2)/b;
  if( (y1<=100-x1) && (a*x1+b*y1==c))
  {
   cout<<x1<<" "<<y1<<endl;} 
   //cout<<x1+y1<<endl;
  if((x1+y1>sum)&&(x1+y1<101)/*&&(x1+y1==99)*/)
   {
    sum=x1+y1;
    
   }

  
  if( (y2<=100-x2) && (a*x2+b*y2==c))
  {
cout<<x2<<" "<<y2<<endl;
  //cout<<x2+y2<<endl;
  }
  if((x2+y2>sum)&&(x2+y2<101)/*&&(x2+y2==99)*/)
  {
   sum=x2+y2;
   
  }
 }

 cout<<sum;
 system("PAUSE");
}

沒有留言:

張貼留言