পাইথনে সিক্কা ও পরিমাণ দিয়ে স্বতন্ত্র কয়েন সম (Distinct Coin Sums) গণনা

সমস্যা বিবরণ

coins এবং quantities লিস্ট দেওয়া আছে। i-তম সিক্কার ভ্যালু coins[i] এবং পরিমাণ quantities[i]। খালি নন-এমপ্টি সাবসেট দিয়ে বানানো যেতে পারে কতগুলো স্বতন্ত্র (distinct) কয়েন সম (sum)?

উদাহরণ

coins = [1, 2, 5]
quantities = [1, 2, 1]

সম্ভাব্য সম:
[1]=1, [2]=2, [1,2]=3, [2,2]=4, [5]=5,
[1,5]=6, [2,5]=7, [1,2,5]=8, [2,2,5]=9, [1,2,2,5]=10

Output: 10

অ্যালগরিদম: রিকার্সিভ ব্যাকট্র্যাকিং + সেট

1. fres = সেট (স্বতন্ত্র সম সংরক্ষণ)
2. rec(i, current_sum) রিকার্সিভ ফাংশন:
   • বেস কেস: i == len(coins) হলে রিটার্ন
   • k = 0 থেকে quantities[i] পর্যন্ত লুপ:
     • new_sum = current_sum + k * coins[i]
     • fres.add(new_sum)
     • rec(i+1, new_sum)
3. len(fres) - 1 রিটার্ন করুন (০ বাদ দিয়ে)

পাইথন কোড

class Solution:
    def solve(self, coins, quantities):
        def rec(i, res):
            if i == len(coins):
                return
            for k in range(quantities[i] + 1):
                cur = res + k * coins[i]
                fres.add(cur)
                rec(i + 1, cur)
        
        fres = set()
        rec(0, 0)
        return len(fres) - 1  # 0 বাদ দিন

ob = Solution()
coins = [1, 2, 5]
quantities = [1, 2, 1]
print(ob.solve(coins, quantities))  # 10

ডাইনামিক প্রোগ্রামিং অপ্টিমাইজেশন (বড় ইনপুটের জন্য)

def solve_dp(coins, quantities):
    max_sum = sum(c * q for c, q in zip(coins, quantities))
    dp = [False] * (max_sum + 1)
    dp[0] = True
    
    for coin, qty in zip(coins, quantities):
        # বাইনারি অপ্টিমাইজেশন (Bounded Knapsack)
        k = 1
        while qty > 0:
            use = min(k, qty)
            qty -= use
            val = use * coin
            for s in range(max_sum, val - 1, -1):
                if dp[s - val]:
                    dp[s] = True
            k <<= 1
    
    return sum(dp) - 1  # 0 বাদ

জটিলতা বিশ্লেষণ

উপসংহার

• ছোট ইনপুটের জন্য ব্যাকট্র্যাকিং + সেট সহজ ও বুঝতে সহজ
• বড় ইনপুট/বড় পরিমাণের জন্য DP + বাইনারি অপ্টিমাইজেশন দরকার
• সেট আটোমেটিক্যালি ডুপ্লিকেট সম হ্যান্ডেল করে