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

ধরুন আমাদের কাছে n আইটেম সহ baseCosts নামক দুটি অ্যারে আছে যেগুলি থেকে আমরা বেস নির্বাচন করতে পারি এবং m আইটেম সহ toppingCosts আমরা টপিং নির্বাচন করতে পারি এবং একটি লক্ষ্য মানও থাকতে পারি। মিষ্টি তৈরি করতে আমাদের এই নিয়মগুলি মেনে চলতে হবে।

• ঠিক একটি বেস থাকতে হবে৷

  ৷

• আমরা এক বা একাধিক টপিং যোগ করতে পারি বা কোনো টপিং নেই৷

• প্রতিটি ধরণের টপিং এর মধ্যে সর্বাধিক দুটি রয়েছে৷

  ৷

এখানে baseCosts[i] ith আইসক্রিম বেসের দামের প্রতিনিধিত্ব করে। টপিং কস্ট[i] ith টপিং এর একটির দামকে প্রতিনিধিত্ব করে। লক্ষ্য মান মিষ্টান্ন জন্য লক্ষ্য মূল্য প্রতিনিধিত্ব করা হয়. যতটা সম্ভব লক্ষ্যের কাছাকাছি মোট খরচ দিয়ে আমাদের একটি মিষ্টি তৈরি করতে হবে। আমরা লক্ষ্য করার জন্য ডেজার্টের সম্ভাব্য সম্ভাব্য খরচ খুঁজে বের করতে হবে। একাধিক উত্তর থাকলে, নিচেরটি ফেরত দিন।

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

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• best_cost :=baseCosts[0]

• b এর জন্য 0 থেকে বেসকস্টের আকার - 1, করুন

  • বিটমাস্ক :=একটি অ্যারে যার আকার টপিং কস্টের আকারের সমান এবং 0 দিয়ে পূরণ করুন

  • নিম্নলিখিত অসীমভাবে করুন, করুন

    • বর্তমান_মূল্য :=ভিত্তিমূল্য[b]

    • j-এর জন্য 0 থেকে বিটমাস্কের আকার - 1, করুন

      • বর্তমান_মূল্য :=বর্তমান_মূল্য + বিটমাস্ক[জে] * টপিং কস্ট[j]

    • যদি বর্তমান_মূল্য - লক্ষ্য 0 এর সমান হয়, তাহলে

      • রিটার্ন টার্গেট

    • অন্যথায় যখন |current_price - লক্ষ্য| <|best_cost - টার্গেট|, তারপর

      • best_cost :=বর্তমান_দাম

    • অন্যথায় যখন |current_price - লক্ষ্য| |best_cost - target| এর মত, তারপর

      • যদি বর্তমান_মূল্য <সেরা_মূল্য, তাহলে

        • best_cost :=বর্তমান_দাম

    • যদি 0 বিটমাস্কে না থাকে এবং 1 বিটমাস্কে না থাকে, তাহলে

      • লুপ থেকে বেরিয়ে আসুন

    • আমি 0 থেকে বিটমাস্কের আকার - 1 এর মধ্যে, কর

      • যদি বিটমাস্ক[i] 2 এর মত না হয়, তাহলে

        • বিটমাস্ক[i] :=বিটমাস্ক[i] + 1

        • লুপ থেকে বেরিয়ে আসুন

      • অন্যথায়,

        • বিটমাস্ক[i] :=0

• ফেরত সেরা_কস্ট

উদাহরণ

আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -

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

আউটপুট

12