高手进来讲解下两个问题：第一个就是求两个数的最大公约数用欧几里德算法和连续检测整数方法？二就是如何用贪心算法求背包问题的啦？

高手进来讲解下两个问题：第一个就是求两个数的最大公约数用欧几里德算法和连续检测整数方法？二就是如何用贪心算法求背包问题的啦？

欧几里得辗转相除

int gcd(int m,int n)

{

if(m < n ) return gcd(n,m);

else if(m % n ==0) return n;

else return (n,m%n);

}

贪心算法求解背包问题不能得到最优解的，对于普通的背包问题，如0-1背包，贪心算法的策略就是每次选取的是性价比最高的东西放进背包，这样一般情况下会得到最优解，但是很容易找到特例说明这个不是最优解。

解背包问题的常见方法为搜索和动态规划，一般选择动态规划，时间复杂度低。