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

Sphere Packing 题号:222 难度: 60 中英对照

What is the length of the shortest pipe, of internal radius 50mm, that can fully contain 21 balls of radii 30mm, 31mm, ..., 50mm?

Give your answer in micrometres (10-6 m) rounded to the nearest integer.

Solution

​ 这个问题可以使用动态规划的思想来求解。我们用下式表示以firstSphere为最下方的球,能装下sphereSet中所有球体的最短管道长度。例如$firstSphere=33000$,$sphereSet=${$30000,33000,34000,41000$},就表示将半径为33000的球体放在最下方,同时要装下它和其他三颗球体的最小管道长度(管道半径题目给定为50000)。 $$ MinLength(firstSphere,sphereSet) $$ 由于,上式子不便直接迭代,使用$MinLength'(firstSphere,sphereSet)$表示MinLength减去最底下那颗球半径后的长度。 * 动态规划问题可以描述为下式,例如$Minlength'(33000,${$30000,33000,34000,41000$})等于$MinLenth'(30000,${$30000,34000,41000$}$)+R(30000,33000)、…、MinLenth'(41000,${$30000,34000,41000$}$)+R(41000,33000)$中的最小值。 $$ MinLength'(firstSphere,sphereSet)=min[MinLength'(i,sphereSet-firstSphere)+R(i,firstSphere)] $$ $$ 其中i\in sphereSet-firstSphere $$ $$ R(i,firstSphere)= \sqrt{(i+firstSphere)-50000)*20000} \quad, i \ne firstSphere $$ $$ R(i,firstSphere)=0 \quad ,i=firstSphere $$ R是i球和firstSphere球在管道中的球心高度差。 * 初值条件如下式所示,即管道要装下的球只有一个时,MinLength’返回这颗球的半径: $$ MinLength'(firstSphere,{firstSphere})=firstSphere $$ 通过动态规则,我们就能得到能装下21个球{30000,31000,32000,…,50000}的最小管道长度

Code

public final class p222 {
	
	public static void main(String[] args) {
		long start = System.nanoTime();
		long result = run();
        long end = System.nanoTime();
		System.out.println( result );
		System.out.println (( end - start )/1000000 +"ms");		
	}
	
	
	public static long run() {
		sphereRadii = new double[21];  // {30000, 31000, 32000, ..., 49000, 50000}
		for (int i = 0; i < sphereRadii.length; i++)
			sphereRadii[i] = (i + 30) * 1000;
		minLength = new double[sphereRadii.length][1 << sphereRadii.length];
		double min = Double.POSITIVE_INFINITY;
		for (int i = 0; i < sphereRadii.length; i++)
			min = Math.min(findMinimumLength(i, (1 << sphereRadii.length) - 1) + sphereRadii[i], min);
		return Math.round(min);
	}
	
	
	private static double[] sphereRadii;  // 保存各个球体的半径
	

	/*使用minLength[i][j]保存最小管长度减去最下方求半径的结果。i用于表示sphereRadii[i]是管中最下方的球,然后j用于表示sphereRadii数组中哪些球是要放入管中的球。。
	 * 例如:sphereRadii=[30000,31000,32000,...,500000] 
	 * minlength[3][0x819]=minlength[3][b2073]=minlength[3][100000011001] ,表示以33000为最下方的球,要放入管中的球为{30000, 33000, 34000, 41000} 
	 * */

	private static double[][] minLength;
	
	private static double findMinimumLength(int currentSphereIndex, int setOfSpheres) {
		if ((setOfSpheres & (1 << currentSphereIndex)) == 0)
			throw new IllegalArgumentException();
		
		if (minLength[currentSphereIndex][setOfSpheres] == 0) {
			double result;
			if (Integer.bitCount(setOfSpheres) == 1)
				result = sphereRadii[currentSphereIndex];  // 当只有一个球放入时,取值为该球的半径
			else {
				result = Double.POSITIVE_INFINITY;
				int newSetOfSpheres = setOfSpheres ^ (1 << currentSphereIndex); // 把当前的球从集合中去掉,算剩下的球
				for (int i = 0; i < sphereRadii.length; i++) { 
					if ((newSetOfSpheres & (1 << i)) == 0) //如果新的要放在第一位置的球体,不在球体集合中
						continue;
					// 计算球i与球currentSphereIndex的球心高度差
					double temp = Math.sqrt((sphereRadii[i] + sphereRadii[currentSphereIndex] - 50000) * 200000);
					temp += findMinimumLength(i, newSetOfSpheres);
					result = Math.min(temp, result);
				}
			}
			minLength[currentSphereIndex][setOfSpheres] = result;
		}
		return minLength[currentSphereIndex][setOfSpheres];
	}
	
}
1590933
10399ms