Python प्रोग्राम - रॉड काटकर और समान लंबाई के रॉड बेचकर अधिकतम लाभ

रॉड की लंबाई की सूची rodLen दी गई है। दो पूर्णांक profit (प्रति यूनिट लंबाई लाभ) और cost (प्रति कट लागत) भी दिए गए हैं। हम प्रति यूनिट लंबाई पर लाभ कमा सकते हैं लेकिन केवल वही रॉड बेच सकते हैं जो सभी समान लंबाई के हों। हम एक रॉड को दो टुकड़ों में काट सकते हैं ताकि उनकी लंबाई पूर्णांक हो, लेकिन प्रत्येक कट के लिए cost चुकाना होगा। हम जितनी बार चाहें काट सकते हैं। हमें अधिकतम लाभ खोजना है।

उदाहरण

इनपुट: rodLen = [7, 10], profit = 6, cost = 4

आउटपुट: 82

व्याख्या: हम लंबाई 7 के रॉड को 5 और 2 में काट सकते हैं। फिर लंबाई 10 के रॉड को दो रॉड में काट सकते हैं, दोनों लंबाई 5 के। फिर सभी 3 रॉड को लंबाई 5 पर बेचें: कुल लाभ (5 + 5 + 5) * 6 - (2 * 4) = 90 - 8 = 82।

एल्गोरिदम

1. n := len(rodLen)
2. यदि n == 0: 0 लौटाएं
3. l_max := max(rodLen)
4. p_max := 0
5. cuts 1 से l_max तक:
   • p_cut := 0
   • प्रत्येक rod_len in rodLen के लिए:
     • यदि rod_len < cuts: जारी रखें
     • c_count := rod_len // cuts
     • total_len := c_count * cuts
     • यदि rod_len == total_len: c_count -= 1
     • curr_profit := total_len * profit - cost * c_count
     • यदि curr_profit < 0: जारी रखें
     • p_cut += curr_profit
   • p_max = max(p_max, p_cut)
6. p_max लौटाएं

Python कार्यान्वयन

def solve(rodLen, profit, cost):
    n = len(rodLen)
    if n == 0:
        return 0
    l_max = max(rodLen)
    p_max = 0
    for cuts in range(1, l_max + 1):
        p_cut = 0
        for rod_len in rodLen:
            if rod_len < cuts:
                continue
            c_count = rod_len // cuts
            total_len = c_count * cuts
            if rod_len == total_len:
                c_count -= 1
            curr_profit = total_len * profit - cost * c_count
            if curr_profit < 0:
                continue
            p_cut += curr_profit
        p_max = max(p_max, p_cut)
    return p_max

rodLen = [7, 10]
profit = 6
cost = 4
print(solve(rodLen, profit, cost))  # आउटपुट: 82

इनपुट/आउटपुट

Input: [7, 10], 6, 4
Output: 82