Question
Transcribed Text
Dynamic Programming
Problem Statement
For this assignment, you will develop a program to demonstrate your understanding of
the use of dynamic programming as an algorithm design technique.
We want to create a long paper chain of triangles for the king of Algroland. This
king requires that the various supply of grey colored paper of triangles be connected
together such that the shades of grey increase from light (white has value 0.0) to dark
(black has value 1.0). Each triangle can be fastened together with one or two other
triangles along sides with equal length. To increase flair, each triangle of the chain must
be a different shade of grey. For example, for the triangles shown in the figure below,
we can connect together four of them to make a chain.
3
4
4
4
4
2
2
2
2
3
6
5
3
4
4
4 4
7
g = 0
g = 0.4
g = 0.6
g = 0.6
g = 0.7
g = 1.0
Input
The input consists of a first line containing an integer 1 ≤ n ≤ 10000 denoting the
number of triangles available. This is then followed by a n lines containing three positive
integers l1, l2, l3 that denote the triangle side lengths and a real value 0.000 ≤ g ≤ 1.000
that denotes the grey scale color.
Output
For each test case output a single positive integer that represents the longest chain
(number of triangles) that could be made.
Taken from the earlier pictorial example we have the following sample input and
expected output.
Sample Input Sample Output
6
3 4 4 0.4
4 4 2 0.0
4 7 4 0.6
2 2 2 0.6
3 5 6 0.7
3 4 4 1.0
4
Solution Preview
This material may consist of step-by-step explanations on how to solve a problem or examples of proper writing, including the use of citations, references, bibliographies, and formatting. This material is made available for the sole purpose of studying and learning - misuse is strictly forbidden.
import java.io.BufferedReader;import java.io.File;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;
public class Algroland {
private static ArrayList<Triangle [] > readFile(String fileName) throws FileNotFoundException, Exception{
Scanner scanner = new Scanner( new File(fileName) );
ArrayList<Triangle [] > list = new ArrayList<Triangle []>();
int i = 0;
int number;
while (scanner.hasNext()) {
number = Integer.parseInt( scanner.nextLine() );
if (number <= 0)
break;
Triangle [] triangles = new Triangle[number];
for (int j = 0; j < number; j++) {
String next = scanner.nextLine();
triangles[j] = new Triangle(next);
}
list.add(triangles);
}
return list;
}...
Return to homework library