মডিউল ২১_৩ঃ Rod Cutting Problem

প্রথমে আপনাকে একটি রড দেয়া হবে। ধরুন সেই রডটির দৈর্ঘ্য ৭।

এখন আপনাকে একটি প্রফিট লিস্ট দেয়া হল , যেইটি দিয়ে আপনি বুঝবেন আপনি রড কেটে কত দৈর্ঘ্য বানালে আপনার কত করে প্রফিট আসবে।

আপনার থেকে বের করতে হবে, আপনাকে দেয়া রডটি কিভাবে কত দৈর্ঘ্য করে কাটলে আপনি সবোচ্ছ প্রফিট করতে পারবেন।

উপরের দেয়া চিত্রটিতে সবোচ্ছ প্রফিটা আসবে 14।

একটু চিন্তা করলে আপনি এই প্রব্লেমটি Knapsack দিয়ে করতে পারবেন, এখন আপনি চিন্তা করে দেখুন এইটি কি 0-1 Knapsack হবে নাকি Unbounded Knapsack হবে।