পাইথনে টার্গেটের সবচেয়ে নিকটবর্তী ডেজার্ট খরচ বের করার প্রোগ্রাম

মনে করুন baseCosts (n আইটেম) এবং toppingCosts (m আইটেম) নামক দুটি অ্যারে এবং একটি target ভ্যালু আছে। ডেজার্ট বানাতে নিচের নিয়ম মানতে হবে:

ঠিক একটি বেস সিলেক্ট করতে হবে।
এক বা একাধিক টপিং যোগ করা যাবে, অথবা কোনো টপিং নাও থাকতে পারে।
প্রতিটি টাইপের টপিং বেশিから ज्यादा দুটি হতে পারে।

baseCosts[i] হলো i-তম আইসক্রিম বেসের দাম। toppingCosts[i] হলো i-তম টপিংয়ের দাম। target হলো ডেজার্টের টার্গেট প্রাইস। টার্গেটের যতটা সম্ভব নিকটবর্তী মোট খরচে ডেজার্ট বানাতে হবে। একাধিক উত্তর হলে কমটিটি রিটার্ন করুন।

যেমন, ইনপুট baseCosts = [2,8], toppingCosts = [4,5], target = 12 হলে, আউটপুট হবে ১২ কারণ বেস ৮, প্রথম টপিং ১টি (খরচ ৪), দ্বিতীয় টপিং ০, মোট ৮+৪ = ১২।

সমাধান পদ্ধতি

এই সমস্যাটি সমাধান করতে নিচের ধাপগুলো অনুসরণ করুন:

best_cost := baseCosts[0]
b = 0 থেকে baseCosts-এর সাইজ - ১ পর্যন্ত
- bitmask := toppingCosts-এর সাইজের একটি অ্যারে ০ দিয়ে ফিল করা
- অনন্ত লুপ চলে
  - current_price := baseCosts[b]
  - j = 0 থেকে bitmask-এর সাইজ - ১ পর্যন্ত
    - 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 এবং 1 bitmask-এ উভয়েই না থাকে, তবে
    - লুপ থেকে বেরিয়ে আসুন
  - i = 0 থেকে bitmask-এর সাইজ - ১ পর্যন্ত
    - যদি bitmask[i] != 2 হয়, তবে
      - 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