Write code that find maximum cuts of an iron bar

Question

I'm currently trying to write a Python programm that can find the maxium cuts for a 5m iron bar. The allowed cuts are : 0.5m, 1m, 1.2m, and 2m. Given that I have to find all the combinations that match or get close to 5m. Combinations exemple:

• 10*0.5 = 5m
• 7*0.5 + 1.2 = 4.7m

The second combination is also good because we cant produce a 0.3m cut so we throw it away. The order inside a combination dosent matter,

7x0.5 + 1.2 = 1.2 + 7x0.5

so we have to count it only once. So ideally my programm take a file in, and write a file with all the combinations like:

c1 = 10*0.5 
c2 = 7*0.5 + 1.2 
....

Can anyone share advice from where to start please ? Thank you.

Answer 1

Perhaps this is what you are looking for ?

x = [2, 1.2, 1, 0.5]
max_val = 5

def find_next(state, idx, check=False):
    if(idx == len(x)):
        return print_it(state, check)
    if(sum(state) + x[idx] > max_val):
        find_next(state, idx + 1, True)
    else:
        find_next(state + [x[idx]], idx)
        find_next(state, idx + 1)

def print_it(state, check):
    if check:
        print("")
        print(sum(state),state)
    return


find_next([],0)

It recursively finds the next value until it runs out of values, and it tracks the current state with a simple list which it prints with print_it function. I will leave the formatting and file storage up to you, which can easily be implemented in that function.