用5,7,12加减运算，求最少步数得到任意数n

package www.viking.com.algorithm;public class MinSteps {/** * @param args *            5,7,12加减运算表示任意n的最少个数 *  *            也就是 5x+7y+12z=n *  *            求|x|+|y|+|z|的最小值 *  *            方法一：动态规划的思想 *  *            首先正数和负数的性质一样的，所以只考虑正数的情况 *            我们用f(n)表示所有的组合方式的5、7、12的最少的个数,因为组合方式有无限多种，我们只关心 *            最少的个数，要尽量向n减小的方向递归。 f(n)=min{f(n-5),f(n-7),f(n -12)}+1; *            f(0)~f(12)是已知的 *  *            动态规划的性能非常低，当n为3位数的时候就已经很慢了 *  *  *            方法二：另外一种更简单的方法,枚举法 *  *            5x+7y+12z=n要使|x|+|y|+|z|的最小值，那么z要尽量的大， 所以x和y就有取值范围了 |x|<7, *            |y|<12. 因为如果x>=7那么 5x=5(x-7)+5*7其中y=5，x-7+5肯定比x小，所以|x|一定小7 *            同理|y|<12。 用枚举法求出最少的|x|+|y|+|z|就可以了。 *  *  */public static void main(String[] args) {int n = -100;int step[] = { 5, 7, 12 };if (n < 0) {step[0] = -5;step[1] = -7;step[2] = -12;}int min1 = minSteps(n, step, "=" + n);int min2 = minSteps(n);System.out.println(min1 + " " + min2);}public static int minSteps(int n, int[] step, String path) {if (n == 5 || n == 7 || n == 12) {//System.out.println(n + path);return 1;} else if (n < 12 && n >= 0) {// 0=5-5// 1=5+5+5-7-7// 2=7-5// 3=5+5-7// 4=7+7-5-5// 6=7+7+7-5-5-5// 8=5+5+5-7// 9=7+7-5// 10=5+5// 11=7+7+7-5-5if (n == 0) {System.out.println("5-5" + path);return 2;}if (n == 1) {System.out.println("5+5+5-7-7" + path);return 5;}if (n == 2) {System.out.println("5-7" + path);return 2;}if (n == 3) {System.out.println("5+5-7" + path);return 3;}if (n == 4) {System.out.println("7+7-5-5" + path);return 4;}if (n == 6) {System.out.println("7+7+7-5-5-5" + path);return 6;}if (n == 8) {System.out.println("5+5+5-7" + path);return 4;}if (n == 9) {System.out.println("7+7-5" + path);return 3;}if (n == 10) {System.out.println("5+5" + path);return 3;}if (n == 11) {System.out.println("7+7+7-5-5" + path);return 5;}}int a[] = new int[3];a[0] = minSteps(n - step[0], step, "+" + step[0] + path);a[1] = minSteps(n - step[1], step, "+" + step[1] + path);a[2] = minSteps(n - step[2], step, "+" + step[2] + path);int min = a[0];for (int i = 1; i < a.length; i++) {if (a[i] != Integer.MAX_VALUE) {if (a[i] < min) {min = a[i];}}}if (min == Integer.MAX_VALUE) {return Integer.MAX_VALUE;}return min + 1;}public static int minSteps(int n) {if (n == 0) {System.out.println("0=(5-5)");return 2;}int z = 0;int min = Integer.MAX_VALUE;int num = 0;for (int x = -6; x < 7; x++) {for (int y = -11; y < 12; y++) {int rest = n - x * 5 - y * 7;if (rest % 12 == 0) {z = rest / 12;// x、y、z不能同时为负数// 因为只能做加减法，5、7、12都是整数，至少有一个数为整if (x > 0 || y > 0 || z > 0) {num = Math.abs(x) + Math.abs(y) + Math.abs(z);if (num < min && num != 0) {System.out.println(n + "=(" + x + "*5)+(" + y+ "*7)+(" + z + "*12)");min = num;}}}}}return min;}}