ন্যাপস্যাক

নির্দেশনা

আপনার কাজ হলো ঠিক কোন কোন আইটেম নিতে হবে তা নির্ধারণ করা, যাতে ন্যাপস্যাকের বহন ক্ষমতা বিবেচনায় নিয়ে তাঁর নির্বাচনের মোট মান সর্বোচ্চ করা যায়।

আইটেমগুলোকে আইটেমের একটি অ্যারে হিসেবে উপস্থাপন করা হবে। প্রতিটি আইটেমের একটি ওজন ও একটি মান থাকবে। প্রদত্ত সব মানই কঠোরভাবে ধনাত্মক হবে। বব প্রতিটি আইটেম থেকে মাত্র একটি করে নিতে পারেন।

উদাহরণস্বরূপ:

Items: [
  { "weight": 5, "value": 10 },
  { "weight": 4, "value": 40 },
  { "weight": 6, "value": 30 },
  { "weight": 4, "value": 50 }
]

Knapsack Maximum Weight: 10

উপরের উদাহরণে প্রথম আইটেমের ওজন ৫ এবং মান ১০, দ্বিতীয় আইটেমের ওজন ৪ এবং মান ৪০, এভাবেই চলতে থাকে। এই উদাহরণে, ববের মান সর্বোচ্চ করতে হলে তাঁর দ্বিতীয় ও চতুর্থ আইটেমটি নেওয়া উচিত, যা এই ক্ষেত্রে ৯০। তিনি ৯০-এর বেশি পেতে পারেন না, কারণ তাঁর ন্যাপস্যাকের ওজনের সীমা ১০।

---

সূত্র

Wikipedia