I will give thumbs up for the answer. I have provided all the documentation needed below. Please let me know if something isn't clear.

Problem B (3 points)

In the cut length problem, the approach described will always result in the fewest number of cuts when using the allowed lengths [20, 10, 5, 2, 1]. Come up with an allowed lengths list containing at least four values for which the greedy algorithm does not result in the fewest number of cuts. Provide the list and a board length, along with the pieces that the algorithm finds and the optimal solution.

This is the cut length problem. Please only do the above based on this one.

You are given a list of allowed lengths for cutting a board of arbitrary length. You need to use the fewest cuts possible to cut the board into pieces of the allowed lengths. That's done by making a greedy choice: cut as many boards at the longest length as possible, then as many of the second longest length with what remains, and so forth. For example, if the allowed lengths are [20, 10, 5, 2, 1], you would cut a board of length 22 into a piece of length 20 and a piece of length 2. If the board is length 19, you would cut it into one length 10 piece, one length 5 piece, and two length 2 pieces.

Write a program called CutLengths.java or cutlengths.py to implement the algorithm described above. Use the list of allowed lengths given above and test your program on (at least) the two boards specified above (length 22 and length 19). The output should be a list of the allowed lengths and the number of pieces. For example, for length 19, the output should be:

Board length 19 Piece size Count 20 0 10 1 5 1 2 2 1 0

Greedy method: Minimizing board cuts

piece_size=[20,10,5,2,1] # define allowed piece_size list, if not sorted in decending order # use ARRAY_NAME.sort(reverse=True) count=[int]*5 # declare a blank int array of same size as allowed piece_size board=int(input(" Enter full length of board: ")) # input from user for the length of board in integer # in python 2.x use raw_input() instead of input()

j=0 # index for count array print('Board Length: '+str(board)) print('Piece Size\tCount') for i in piece_size: # check from the first possible piece size count[j]=int(board/i) # maximum possible count of piece of current size board=board%i # leave the remainder for next allowed piece_size print(str(i)+'\t'+str(count[j])) # print output j=j+1 # increase index of countarray by 1