Suppose we have a problem where we need

6 pieces of 61 cm of pipe to be cut

5 pieces of 27 cm of pipe to be cut

4 pieces of 67.97 cm of pipe to be cut (fake data)

The manufacturer makes the pipes in

12 cm

24 cm

36 cm

48 cm

60 cm

72 cm

84 cm

96 cm

120 cm lengths (actual what I need)

we want optimize the problem by reducing the amount of waste.

Rule: Each piece of pipe we cut must be shorter than or equal to the length of the piece we cut from leftover pieces from cut pipes can NOT be combined

Example: We cut 61 cm from a 96 cm pipe. We have 35 cm left. We can use this 35 cm piece and cut a 24 cm piece from it. We have 11 cm left. We Cannot however combine 11 cm pieces together to create a longer piece. 11 cm is considered waste.

I tried a python code to return waste and a list of the number of each manufacturers length. Apparently, google says I can use "dynamic programming to solve this problem, but idk how to implement it. I just need an algorithm that I can code, not necessarily just thecode for the problem.

I tried using ChatGPT for some basic help with it, and I still got stuck.

MY CODE:

------------------------------------------------------------------------------------------------------- def min_waste(pieces, lengths): # create a 3D table to store the results of subproblems dp = [[[0 for _ in range(len(lengths)+1)] for _ in range(len(lengths)+1)] for _ in range(len(pieces)+1)] # initialize the table with maximum possible value for i in range(len(pieces)+1): for j in range(len(lengths)+1): for k in range(len(lengths)+1): dp[i][j][k] = float('inf') # base case: if we need 0 pieces of a given length, the waste is 0 for j in range(len(lengths)+1): for k in range(len(lengths)+1): dp[0][j][k] = 0 # solve the subproblems for i in range(1, len(pieces)+1): for j in range(1,len(lengths)+1): for k in range(len(lengths)+1): if pieces[i-1] <= lengths[j-1]: # if we can fit the current piece in the current length, try to fit it # and see if it leads to less waste than the previous solution dp[i][j][k] = min(dp[i][j][k], dp[i-1][j][k] + lengths[j-1] - pieces[i-1]) if k > 0: # if we can't fit the current piece in the current length, try to fit it # in a longer length and see if it leads to less waste dp[i][j][k] = min(dp[i][j][k], dp[i-1][j][k-1]) # the minimum waste is the value in the bottom right corner of the table return dp[-1][-1][-1] # test the function pieces = [61, 27, 67.93] lengths = [12, 24, 36, 48, 60, 72, 84, 96, 120] print(min_waste(pieces, lengths))