Ideone.com

download

copy

 
 
import static java.lang.Math.max;
 
import java.util.concurrent.ThreadLocalRandom;
 
public class Main {
 
	static int[] priceTable = new int[11];
 
 
	public static void main(String[] args) {
		for (int i = 0; i < 50; i++)
		{
			for (int j = 0; j < priceTable.length; j++)
			{
				priceTable[j] = ThreadLocalRandom.current().nextInt(100);
			}
			for (int k = 0; k < 10; k++)
			{
				System.out.println(cormenCutRod(k)+" - "+cutRodM(k));
 
			}
		}
 
 
	}
 
	public static int cormenCutRod(int lenght) {
 
		if (lenght == 0)
		{
			return 0;
		}
		int q = 0;
		for (int i = 1; i <= lenght; i++)
		{
			q = max(q, priceTable[i] + cormenCutRod(lenght - i));
		}
 
		return q;
	}
 
	static int cutRodM(int lenght) {
 
		int[] mem = new int[lenght + 1];
		mem[0] = 0;
		int i, j;
		// filling the table bottom up
		for (i = 1; i <= lenght; i++)
		{
			int q = 0;
			for (j = 1; j <= i; j++)
				q = max(q, priceTable[j] + mem[i - j]);
			mem[i] = q;
		}
 
		return mem[lenght];
	}
}

Success #stdin #stdout 0.09s 380480KB

stdin

copy

Standard input is empty

stdout

copy

Discover > Sphere Engine API

Discover > IDE Widget

Discover > Sphere Engine API

Discover > IDE Widget

Choose your language