求一个贪心算法
给定一个含有三个数字的数据（m，n，t），其中m,n,t皆为正整数，求正整数a，b，使得am+bn达到最大但不超过t（这个是大前提），同时a+b最大
譬如说
（3，2，10）的话，a=0，b=5，am+bn为10；
（5，41，112）的话，a=6，b=2，am+bn=112
（253，234，1919），a=2，b=6，am+bn=1910
简单来讲，就是保证最大程度接近t，在这个前提下使a+b最大
求教！
[解决办法]
import java.util.*;
public class diet{
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
int factorM = 0;
int factorN = 0;
int tempM = 0;
int tempN = 0;
int sum = 0;
int difference = 0;
int m = sc.nextInt();
int n = sc.nextInt();
int t = sc.nextInt();
while(m!=0&&n!=0&&t!=0){
if(m < n){
if(t%m==0){
factorM = t / m;
difference = 0;
}
else{
tempM = t / m;
tempN = (t - m * tempM) / n;
sum = m*tempM + tempN*n;
difference = t - sum;
//System.out.println("Start: tempM is " + tempM);
int times = tempM+1;
for(int i = 0; i < times; i++){
tempN = (t - m * tempM) / n;
//System.out.println("tempN is " + tempN);
sum = m*tempM + tempN*n;
//System.out.println("sum is " + sum);
if(t - sum < difference){
difference = t - sum;
factorM = tempM;
factorN = tempN;
tempM--;
}else if(t - sum == difference){
if(factorM+factorN < tempM+tempN){
factorM = tempM;
factorN = tempN;
}
tempM--;
}else{
tempM--;
}
}
}
System.out.println(factorM+factorN + " " + difference);
//System.out.println("factorM: " + factorM + " factorN: " + factorN + " difference: " + difference);
factorM = 0;
factorN = 0;
}else if(m > n){
if(t%n==0){
factorM = t / n;
difference = 0;
}else{
tempN = t / n;
tempM = (t - n * tempN) / m;
sum = m*tempM + tempN*n;
difference = t - sum;
//System.out.println("Start: tempM is " + tempM);
int times = tempN+1;
for(int i = 0; i < times; i++){
tempM = (t - n * tempN) / m;
//System.out.println("tempN is " + tempN);
sum = m*tempM + tempN*n;
//System.out.println("sum is " + sum);
if(t - sum < difference){
difference = t - sum;
factorM = tempM;
factorN = tempN;
tempN--;
}else if(t - sum == difference){
if(factorM+factorN < tempM+tempN){
factorM = tempM;
factorN = tempN;
}
tempN--;
}else{
tempN--;
}
}
}
System.out.println(factorM+factorN + " " + difference);
//System.out.println("factorM: " + factorM + " factorN: " + factorN + " difference: " + difference);
factorM = 0;
factorN = 0;
}else{
factorM = t / m;
factorN = 0;
sum = m * factorM;
difference = t - sum;
System.out.println(factorM+factorN + " " + difference);
//System.out.println("factorM: " + factorM + " factorN: " + factorN + " difference: " + difference);
factorM = 0;
factorN = 0;
}
m = sc.nextInt();
n = sc.nextInt();
t = sc.nextInt();
}
}
}
