Problem: একজন চোর একটি ঘরে ঢুকে দেখলো সেখানে n<=100 ধরণের পণ্য আছে। প্রতি প্রকারের পণ্যের সংখ্যা সর্বোচ্চ cnt[i]<=1000 এবং প্রতি প্রকারের একটি পণ্যের ওজন wt[i]<=1000 এবং প্রতিটি পণ্য চুরি করলে সর্বোচ্চ লাভ profit[i]<=10000। এখন, ঐ চোরের কাছে থাকা ব্যাগে সর্বোচ্চ 10000 KG ওজনের পণ্য নেয়া গেলে চোর সর্বোচ্চ কত লাভ করতে পারবো? Solution: মনে কর, ১টি পণ্যের সংখ্যা ১০ ইউনিট এবং প্রতি ইউনিটের দাম ৩টাকা করে। আমার অপ্টিমাল এন্সারে সেই পণ্যটি ০, ১, ২, ৩, ৪, ৫, ৬, ৭, ৮, ৯ অথবা ১০ বার থাকতে পারে। এবং এর জন্য আমার লাভ হবে যথাক্রমে ০, ৩, ৬, ৯, ১২, ১৫, ১৮, ২১, ২৪, ২৭ অথবা ৩০ টাকা। এখন, আমি যদি ঐ প্রকারের পণ্যের ১ ইউনিট নিয়ে একটি কম্বো প্যাক, ২ ইউনিট নিয়ে একটি কম্বো প্যাক, ৪ ইউনিট নিয়ে একটি কম্বো প্যাক এবং ৩ ইউনিট নিয়ে একটি কম্বো প্যাক বানিয়ে নেই তাহলে আমি ঐ প্রকারের ১০ টি পণ্যের পরিবর্তে নতুন ৪ প্রকারের পণ্য পাবো যারা প্রত্যেকে ১ ইউনিট করে আছে। এবং এই চার প্রকারের পণ্যের দাম যথাক্রমে ৩, ৬, ১২, ৯ টাকা। এখন ভালো করে লক্ষ্য করলে দেখবে যে এই চারটি পণ্যের সাবসেট দ্বারা আমি ০, ৩, ৬, ৯...
Comments
Post a Comment