पायथन में छड़ काटने और समान लंबाई की छड़ें बेचने के बाद अधिकतम लाभ खोजने का कार्यक्रम

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

इसलिए, यदि इनपुट रॉडलेन की तरह है =[7, 10] लाभ =6 लागत =4, तो आउटपुट 82 होगा, क्योंकि हम लंबाई 7 की छड़ को दो छड़ों में काट सकते हैं, लंबाई 5 और 2 के साथ। हम तब कर सकते हैं लंबाई 10 की छड़ को दो छड़ों में काटें, दोनों की लंबाई 5। फिर लंबाई 5 की सभी 3 छड़ें (5 + 5 + 5) * 6 - (2 * 4) =82 के कुल लाभ के लिए बेच दें।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

n :=रॉडलेन का आकार
यदि n, 0 के समान है, तो
- वापसी 0
l_max :=अधिकतम रॉडलेन
p_max :=0
1 से l_max तक की कटौती के लिए, करें
- p_cut :=0
- रॉडलेन में प्रत्येक रॉड_लेन के लिए, करें
  - अगर रॉड_लेन <काटता है, तो
    - अगले पुनरावृत्ति के लिए जाएं
  - c_count :=rod_len / cuts
  - total_len :=c_count * कट्स
  - अगर रॉड_लेन टोटल_लेन के समान है, तो
    - c_count :=c_count - 1
  - curr_profit :=total_len * लाभ - लागत * c_count
  - यदि कर_लाभ <0, तो
    - अगले पुनरावृत्ति के लिए जाएं
  - p_cut :=p_cut + curr_profit
- p_max :=अधिकतम p_max और p_cut
पी_मैक्स लौटाएं

उदाहरण

आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -

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))

इनपुट

[7, 10], 6, 4