Maximize the Cut Segments

Given a rod of length L, the task is to cut the rod in such a way that the total number of segments of length p, q, and r is maximized. The segments can only be of length p, q, and r.

loop_invariant

• initialization_phase will have an array dp defined of length of rod with -1 values. dp 0th value will be 0 so if the length rod is 0 then total pieces will be 0.
• maintenance_phase will have loop that will iterate the length of rod times. The first iteration will execute since dp 0 is 0. Keep updating values in dp array if i and one of rope length is greater than main rope length then pick the max of dp i + p role position and dp i position plus 1
• termination_phase return the last value of array if last value is -1 return 0.

Dynamic programming

# Python 3 program to
# maximize the number
# of segments of length
# p, q and r
 
# Function that returns
# the maximum number
# of segments possible
 
 
def findMaximum(l, p, q, r):
 
    # Array to store the cut
    # at each length
    # All values with -1
    dp = [-1]*(l + 1)
 
    # if length of rod is 0 then
    # total cuts will be 0
    # so, initialize the dp[0] with 0
    dp[0] = 0
 
    for i in range(l+1):
 
        # if certain length is not
        # possible
        print(dp)
        print(dp[i])
        if (dp[i] == -1):
            continue
 
        # if a segment of p is possible
        if (i + p <= l):
            dp[i + p] = (max(dp[i + p],
                             dp[i] + 1))
 
        # if a segment of q is possible
        if (i + q <= l):
            dp[i + q] = (max(dp[i + q],
                             dp[i] + 1))
 
        # if a segment of r is possible
        if (i + r <= l):
            dp[i + r] = (max(dp[i + r],
                             dp[i] + 1))
 
    # if no segment can be cut then return 0
    if dp[l] == -1:
        dp[l] = 0
    # return value corresponding
    # to length l
    return dp[l]
 
 
# Driver Code
if __name__ == "__main__":
    l = 11
    p = 2
    q = 3
    r = 5
 
    # Calling Function
    ans = findMaximum(l, p, q, r)
    print(ans)

In Javascript from ChatGPT

function findMaximum(l, p, q, r) {
    // Array to store the cut
    // at each length
    // All values with -1
    const dp = Array(l + 1).fill(-1);
 
    // if length of rod is 0 then
    // total cuts will be 0
    // so, initialize the dp[0] with 0
    dp[0] = 0;
 
    for (let i = 0; i <= l; i++) {
        // if certain length is not
        // possible
        console.log(dp);
        console.log(dp[i]);
        if (dp[i] === -1) {
            continue;
        }
 
        // if a segment of p is possible
        if (i + p <= l) {
            dp[i + p] = Math.max(dp[i + p], dp[i] + 1);
        }
 
        // if a segment of q is possible
        if (i + q <= l) {
            dp[i + q] = Math.max(dp[i + q], dp[i] + 1);
        }
 
        // if a segment of r is possible
        if (i + r <= l) {
            dp[i + r] = Math.max(dp[i + r], dp[i] + 1);
        }
    }
 
    // if no segment can be cut then return 0
    if (dp[l] === -1) {
        dp[l] = 0;
    }
    // return value corresponding
    // to length l
    return dp[l];
}
 
// Driver Code
const l = 11;
const p = 2;
const q = 3;
const r = 5;
 
// Calling Function
const ans = findMaximum(l, p, q, r);
console.log(ans);