Transcribed TextTranscribed 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 PreviewSolution Preview

These solutions may offer step-by-step problem-solving explanations or good writing examples that include modern styles of formatting and construction of bibliographies out of text citations and references. Students may use these solutions for personal skill-building and practice. Unethical use is strictly forbidden.

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)
            Triangle [] triangles = new Triangle[number];
            for (int j = 0; j < number; j++) {
                String next = scanner.nextLine();               
                triangles[j] = new Triangle(next);
       return list;

By purchasing this solution you'll be able to access the following files:

for this solution

or FREE if you
register a new account!

PayPal, G Pay, ApplePay, Amazon Pay, and all major credit cards accepted.

Find A Tutor

View available Java Programming Tutors

Get College Homework Help.

Are you sure you don't want to upload any files?

Fast tutor response requires as much info as possible.

Upload a file
Continue without uploading

We couldn't find that subject.
Please select the best match from the list below.

We'll send you an email right away. If it's not in your inbox, check your spam folder.

  • 1
  • 2
  • 3
Live Chats