পাইথনে টার্গেট পেতে আমরা কতগুলো উপায় খুঁজে বের করতে পারি?

ধরুন আমাদের কাছে নম নামক অ-ঋণাত্মক সংখ্যার একটি তালিকা রয়েছে এবং একটি পূর্ণসংখ্যা লক্ষ্যও রয়েছে। আমাদের + এবং - সাজানোর উপায়গুলির সংখ্যা খুঁজে বের করতে হবে যাতে অভিব্যক্তিটি লক্ষ্যের সমান হয়।

সুতরাং, ইনপুট যদি nums =[2, 3, 3, 3, 2] টার্গেট =9 এর মত হয়, তাহলে আউটপুট হবে 2, যেমন আমাদের থাকতে পারে -2 + 3 + 3 + 3 + 2 এবং 2 + 3 + 3 + 3 – 2।

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

• s :=সংখ্যায় সমস্ত সংখ্যার যোগফল

• যদি (s + লক্ষ্য) মোড 2 0 বা লক্ষ্য> s এর মত না হয়, তাহলে

  • রিটার্ন 0

• W :=(s + লক্ষ্য) / 2

  এর ভাগফল

• dp1 :=আকারের একটি তালিকা (W + 1) এবং 0

  দিয়ে পূরণ করুন

• dp1[0] :=1

• dp2 :=আকারের একটি তালিকা (W + 1) এবং 0

  দিয়ে পূরণ করুন

• আমি 0 থেকে সংখ্যার আকারের মধ্যে, কর

  • 0 থেকে W + 1 রেঞ্জে j এর জন্য, করুন

    • যদি j>=সংখ্যা[i] হয়, তাহলে

      • dp2[j] :=dp2[j] + dp1[j - সংখ্যা[i]]

  • 0 থেকে W + 1 রেঞ্জে j এর জন্য, করুন

    • dp1[j] :=dp1[j] + dp2[j]

    • dp2[j] :=0

• dp1

  এর শেষ উপাদান ফেরত দিন

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

উদাহরণ

class Solution:
   def solve(self, nums, target):
      s = sum(nums)
      if (s + target) % 2 != 0 or target > s:
         return 0
      W = (s + target) // 2
      dp1 = [0] * (W + 1)
      dp1[0] = 1
      dp2 = [0] * (W + 1)
      for i in range(len(nums)):
         for j in range(W + 1):
            if j >= nums[i]:
               dp2[j] += dp1[j - nums[i]]
            for j in range(W + 1):
               dp1[j] += dp2[j]
               dp2[j] = 0
         return dp1[-1]

ob = Solution()
nums = [2, 3, 3, 3, 2]
target = 9
print(ob.solve(nums, target))

ইনপুট

[2, 3, 3, 3, 2], 9

আউটপুট

2