/ RodCutting Public

Huffman Tree Implementation of The Rod Cutting Problem for CAS 6O03 - Operations Research, McMaster University

# MichaelLiut/RodCutting

Switch branches/tags
Could not load branches
Nothing to show

# Name already in use

A tag already exists with the provided branch name. Many Git commands accept both tag and branch names, so creating this branch may cause unexpected behavior. Are you sure you want to create this branch?

## Files

Failed to load latest commit information.
Type
Name
Commit time

Huffman Tree Implementation of The Rod Cutting Problem
======

Operations Research - CAS 6O03 - McMaster University

--------------------
--------------------
THE QUESTION:

Your boss asks you to cut a wood stick into pieces. The stick-cutting company,
Machinery Asynchronous Cutting Inc. (MAC), charges money according to the length
of the stick being cut. Different selections in the order of cutting can led to
different prices. For example, consider a stick of length 10 meters that has to
be cut at 2, 4 and 7 meters from one end. There are several choices. One can be
cutting first at 2, then at 4, then at 7. This leads to a price of 10+8+6 = 24
because the first stick was of 10 meters, the resulting of 8 and the last one of
6. Another choice could be cutting at 4, then at 2, then at 7. This would lead
to a price of 10+4+6=20, which is a better price.

Let n be the number of cutting points of a stick, you are asked to write an
O(n^3) algorithm to find out the minimum cost for cutting a given stick.
--------------------
--------------------
INPUT:

The first line of each test case will contain a positive number l that
represents the length of the stick to be cut. You can assume l < 1000. The next
line will contain the number n (n < 50) of cuts to be made.

The next line consists of n positive numbers ci (0 < ci < l) representing the
places where the cuts have to be done, given in strictly increasing order.
e.g.:
100
3
25 50 75
--------------------
--------------------
OUTPUT:

You have to print the cost of the optimal solution of the cutting problem, that
is the minimum cost of cutting the given stick.
e.g., the output for the above input should be:
200

======
Completed by Michael Liut, M. Eng, McMaster University
======

Huffman Tree Implementation of The Rod Cutting Problem for CAS 6O03 - Operations Research, McMaster University

## Releases

No releases published

## Packages 0

No packages published