Day 16 - Python

Saree Weaving Optimization using Dynamic Programming

Problem Statement:

You are tasked with optimizing the production of sarees on a weaving machine. Each saree consists of multiple threads woven together in a specific pattern. The weaving process involves selecting threads of different colors and interlacing them to create intricate designs. However, certain designs may require different configurations of threads and take varying amounts of time to weave. Additionally, the machine may need to undergo maintenance at regular intervals, causing downtime.

Your goal is to devise a dynamic programming solution to determine the optimal sequence of thread configurations to maximize the total number of sarees produced within a given time period, considering both the time taken to weave each design and the downtime required for maintenance.

Input:

The number of available thread configurations (N).

An array representing the time taken to weave each design (time[N]).

An array representing the number of sarees produced by each design (sarees[N]).

The maximum time interval before maintenance is required (max_maintenance_time).

Output:

The maximum number of sarees that can be produced within the given time period.

Constraints:

1 <= N <= 1000

1 <= time[i], sarees[i] <= 100

1 <= max_maintenance_time <= 10000

Dynamic Programming Approach:

Define a DP table dp[] where dp[i] represents the maximum number of sarees that can be produced up to the ith design.

Initialize dp[0] = 0, as no sarees are produced initially.

Iterate through each design (i = 1 to N) and for each design:

Check if it's feasible to select this design without exceeding the maximum maintenance time.

Determine the maximum number of sarees produced if we select this design or skip it.

Update dp[i] accordingly.

Return dp[N], which represents the maximum number of sarees produced considering all designs.

Pseudocode:

Function maxSareesProduced(N, time[], sarees[], max_maintenance_time):

    Initialize dp[] with size N+1 and set dp[0] = 0

    For i = 1 to N:

        dp[i] = dp[i-1]  

        For j = i-1 downto 0:

            If time[i] + (i - j - 1) <= max_maintenance_time:

                dp[i] = max(dp[i], dp[j] + sarees[i])  

    Return dp[N]

This dynamic programming approach efficiently considers all possible combinations of thread configurations while ensuring that maintenance intervals are respected, thus providing an optimized solution for maximizing saree production on the weaving machine.

Sample Input:

5

2 3 4 5 6

7 9 18 6 3

7

Output:

43

SOLUTION:

def maxSareesProduced(N, time, sarees, maintenanceTime):

    dp = [0] * (N + 1)

    for i in range(1, N + 1):

        dp[i] = dp[i - 1]  

        for j in range(i - 1, -1, -1):

            if time[i - 1] + (i - j - 1) <= maintenanceTime:

                dp[i] = max(dp[i], dp[j] + sarees[i - 1]) 

    return dp[N]

n = int(input())

time = list(map(int, input().split()))

sarees = list(map(int, input().split()))

maintenanceTime = int(input())

result = maxSareesProduced(n, time, sarees, maintenanceTime)

print(result)

Math Explanation:

For design 1:

i = 1

The inner loop (for j in range(i - 1, -1, -1)) iterates over j = 0. Since i - j - 1 = 1 - 0 - 1 = 0, time[i - 1] + (i - j - 1) = time[0] + 0 = 2, which is less than or equal to maintenanceTime. So, dp[1] = max(dp[1], dp[0] + sarees[0]) = max(0, 0 + 7) = 7.

For design 2:

i = 2

The inner loop (for j in range(i - 1, -1, -1)) iterates over j = 1, 0.

For j = 1: time[i - 1] + (i - j - 1) = time[1] + (2 - 1 - 1) = 3 + 0 = 3, which is less than or equal to maintenanceTime. So, dp[2] = max(dp[2], dp[1] + sarees[1]) = max(7, 7 + 9) = 16.

For j = 0: time[i - 1] + (i - j - 1) = time[1] + (2 - 0 - 1) = 3 + 1 = 4, which is less than or equal to maintenanceTime. So, dp[2] = max(dp[2], dp[0] + sarees[1]) = max(16, 0 + 9) = 16.

For design 3:

i = 3

The inner loop (for j in range(i - 1, -1, -1)) iterates over j = 2, 1, 0.

For j = 2: time[i - 1] + (i - j - 1) = time[2] + (3 - 2 - 1) = 4 + 0 = 4, which is less than or equal to maintenanceTime. So, dp[3] = max(dp[3], dp[2] + sarees[2]) = max(16, 16 + 18) = 34.

For j = 1: time[i - 1] + (i - j - 1) = time[2] + (3 - 1 - 1) = 4 + 1 = 5, which is less than or equal to maintenanceTime. So, dp[3] = max(dp[3], dp[1] + sarees[2]) = max(34, 7 + 18) = 34.

For j = 0: time[i - 1] + (i - j - 1) = time[2] + (3 - 0 - 1) = 4 + 2 = 6, which is less than or equal to maintenanceTime. So, dp[3] = max(dp[3], dp[0] + sarees[2]) = max(34, 0 + 18) = 34.

For design 4:

i = 4

The inner loop (for j in range(i - 1, -1, -1)) iterates over j = 3, 2, 1, 0.

For j = 3: time[i - 1] + (i - j - 1) = time[3] + (4 - 3 - 1) = 5 + 0 = 5, which is less than or equal to maintenanceTime. So, dp[4] = max(dp[4], dp[3] + sarees[3]) = max(34, 34 + 6) = 40.

For j = 2: time[i - 1] + (i - j - 1) = time[3] + (4 - 2 - 1) = 5 + 1 = 6, which is less than or equal to maintenanceTime. So, dp[4] = max(dp[4], dp[2] + sarees[3]) = max(40, 16 + 6) = 40.

For j = 1: time[i - 1] + (i - j - 1) = time[3] + (4 - 1 - 1) = 5 + 2 = 7, which is less than or equal to maintenanceTime. So, dp[4] = max(dp[4], dp[1] + sarees[3]) = max(40, 7 + 6) = 40.

For j = 0: time[i - 1] + (i - j - 1) = time[3] + (4 - 0 - 1) = 5 + 3 = 8, which is greater than maintenanceTime, so this option is skipped.

For design 5:

i = 5

The inner loop (for j in range(i - 1, -1, -1)) iterates over j = 4, 3, 2, 1, 0.

For j = 4: time[i - 1] + (i - j - 1) = time[4] + (5 - 4 - 1) = 6 + 0 = 6, which is less than or equal to maintenanceTime. So, dp[5] = max(dp[5], dp[4] + sarees[4]) = max(40, 40 + 3) = 43.

For j = 3: time[i - 1] + (i - j - 1) = time[4] + (5 - 3 - 1) = 6 + 1 = 7, which is equal to maintenanceTime. So, dp[5] = max(dp[5], dp[3] + sarees[4]) = max(43, 34 + 3) = 43.

For j = 2: time[i - 1] + (i - j - 1) = time[4] + (5 - 2 - 1) = 6 + 2 = 8, which is greater than maintenanceTime, so this option is skipped.

For j = 1: time[i - 1] + (i - j - 1) = time[4] + (5 - 1 - 1) = 6 + 3 = 9, which is greater than maintenanceTime, so this option is skipped.

For j = 0: time[i - 1] + (i - j - 1) = time[4] + (5 - 0 - 1) = 6 + 4 = 10, which is greater than maintenanceTime, so this option is skipped.

Insights:

• The state is represented by the dp array, where dp[i] represents the maximum number of sarees produced up to the i-th design configuration.
• The dp array is initialized with zeros, indicating that initially, no sarees are produced.
• The code iterates through each design configuration (i) and updates the dp array based on the previous configurations and constraints.
• There are nested loops used in the code. The outer loop iterates through each design configuration, and the inner loop iterates through the previous designs to compute the maximum number of sarees produced.
• The code considers the time constraints for each design configuration to ensure that the total time spent on maintenance does not exceed the maximum maintenance time.
• By utilizing dynamic programming, the code finds the optimal solution by considering all possible combinations of design configurations.
• The dp array is optimized to store only the necessary information, leading to memory efficiency.

Embark on the journey of coding, where each line of code weaves intricate patterns mirroring the elegance of Kancheepuram sarees!!

Happy Coding!