当前位置:首页 » Project Euler » 详细页

Maximising a weighted product 题号:190 难度: 50 中英对照

Let Sm = (x1, x2, ... , xm) be the m-tuple of positive real numbers with x1 + x2 + ... + xm = m for which Pm = x1 * x22 * ... * xmm is maximised.

For example, it can be verified that [P10] = 4112 ([ ] is the integer part function).

Find Σ[Pm] for 2 ≤ m ≤ 15.

Solution

利用二分的思想,对初始化的数组$a_1=a_2=...=a_m=1.0$,给定一个扰动$var$,对$\forall i,j$将$a_i-=var,a_j+=var$,对扰动后的数组求$P_m$值,所有扰动的情况与不扰动的情况取$P_m$较大者,之后将$var$折半再操作,直至$var$足够小即可。

Code


public final class p190 {
    public static void main(String[] args) {
        long start=System.nanoTime();
        String result = run();        
        long end=System.nanoTime();
        System.out.println(result);
        System.out.println( (end-start)/1000000 + "ms" );
    }


    static public String run() {
		int sum = 0;
		for (int m = 2; m <= 15; m++) {
			double x[] = new double[m];
			double test[] = new double[m];
			double product = 1.0;
			double test_product = 1.0;
			for (int i = 0; i < m; i++) {
				x[i] = 1.0;
				test[i] = 1.0;
			}
			for (int i = 0; i < m; i++)
				product *= Math.pow(x[i], i + 1);
			boolean hit = true;
			double val = 1.0;
			while (hit || val > 0.00001) {//扰动足够小,hit表示是否能命中一个较小值,如果一直能命中更小的,那么也需要继续下去
				if (hit)
					hit = false;
				else
					val *= 0.5;
				//记录i和j
				int add = 0;
				int sub = 0;
				double max = product;
				for (int i = 0; i < m; i++) {
					for (int j = 0; j < m; j++) {
						if (i != j) {
							for (int k = 0; k < m; k++)
								test[k] = x[k];
							test_product = 1.0;
							test[i] += val;
							test[j] -= val;
							for (int k = 0; k < m; k++)
								test_product *= Math.pow(test[k], k + 1);
							if (test_product > max) {
								max = test_product;
								add = i;
								sub = j;
								hit = true;
							}
						}
					}
				}
				if (hit) {
					x[add] += val;
					x[sub] -= val;
					product = 1.0;
					for (int k = 0; k < m; k++)
						product *= Math.pow(x[k], k + 1);
				}
			}
			sum += (int) product;
		}
		return sum+"";
    }


}
371048281
78ms