पायथन में निकटतम डेज़र्ट लागत ज्ञात करने का प्रोग्राम

मान लीजिए हमारे पास baseCosts नामक दो सरणियाँ हैं जिनमें n आइटम हैं जिनसे हम बेस चुन सकते हैं और toppingCosts जिनमें m आइटम हैं जिनसे हम टॉपिंग चुन सकते हैं और एक लक्ष्य मान भी है। हमें डेज़र्ट बनाने के लिए इन नियमों का पालन करना होगा।

ठीक एक बेस होना चाहिए।
हम एक या अधिक टॉपिंग जोड़ सकते हैं या बिल्कुल भी टॉपिंग नहीं ले सकते।
प्रत्येक प्रकार के टॉपिंग के अधिकतम दो हो सकते हैं।

यहां baseCosts[i] i-वें आइसक्रीम बेस की कीमत दर्शाता है। toppingCosts[i] i-वें टॉपिंग की कीमत दर्शाता है। लक्ष्य मान डेज़र्ट के लिए लक्ष्य कीमत दर्शाता है। हमें कुल लागत के साथ एक डेज़र्ट बनाना है जो लक्ष्य के जितना संभव हो उतना करीब हो। हमें लक्ष्य के निकटतम संभव डेज़र्ट लागत को ढूंढना है। यदि कई उत्तर हैं, तो निचला वाला वापस करें।

इसलिए, यदि इनपुट है baseCosts = [2,8], toppingCosts = [4,5], target = 12, तो आउटपुट 12 होगा क्योंकि हम 8 लागत वाला बेस ले सकते हैं, फिर पहले टॉपिंग का 1 जिसकी लागत 4 है, और कोई टाइप2 टॉपिंग नहीं, इसलिए कुल लागत 8+4 = 12।

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

best_cost := baseCosts[0]
b को 0 से baseCosts के आकार - 1 तक के लिए, करें
- bitmask := एक सरणी जिसका आकार toppingCosts के आकार के समान हो और 0 से भरी हो
- निम्न को अनंत बार करें
  - current_price := baseCosts[b]
  - j को 0 से bitmask के आकार - 1 तक के लिए, करें
    - current_price := current_price + bitmask[j] * toppingCosts[j]
  - यदि current_price - target, 0 के समान है, तो
    - target वापस करें
  - अन्यथा जब |current_price - target| < |best_cost - target|, तो
    - best_cost := current_price
  - अन्यथा जब |current_price - target|, |best_cost - target| के समान है, तो
    - यदि current_price < best_cost, तो
      - best_cost := current_price
  - यदि 0 bitmask में नहीं है और 1 bitmask में नहीं है, तो
    - लूप से बाहर आएं
  - i को 0 से bitmask के आकार - 1 तक के लिए, करें
    - यदि bitmask[i], 2 के समान नहीं है, तो
      - bitmask[i] := bitmask[i] + 1
      - लूप से बाहर आएं
    - अन्यथा,
      - bitmask[i] := 0
best_cost वापस करें

उदाहरण

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

def solve(baseCosts, toppingCosts, target):
    best_cost = baseCosts[0]
    for b in range(len(baseCosts)):
        bitmask = [0] * len(toppingCosts)
        while True:
            current_price = baseCosts[b]
            for j in range(len(bitmask)):
                current_price += bitmask[j] * toppingCosts[j]
            if current_price - target == 0:
                return target
            elif abs(current_price - target) < abs(best_cost - target):
                best_cost = current_price
            elif abs(current_price - target) == abs(best_cost - target):
                if current_price < best_cost:
                    best_cost = current_price
            if 0 not in bitmask and 1 not in bitmask:
                break
            for i in range(len(bitmask)):
                if bitmask[i] != 2:
                    bitmask[i] += 1
                    break
                else:
                    bitmask[i] = 0
    return best_cost

baseCosts = [2,8]
toppingCosts = [4,5]
target = 12
print(solve(baseCosts, toppingCosts, target))

इनपुट

[2,8], [4,5], 12