পাইথনে ভগ্নাংশের ন্যাপস্যাক সমস্যা বাস্তবায়নের জন্য প্রোগ্রাম

ধরুন আমাদের দুটি তালিকা আছে, ওজন এবং মান একই দৈর্ঘ্যের এবং আরেকটি মান ক্ষমতা। ওজন[i] এবং মান [i] ith উপাদানের ওজন এবং মান উপস্থাপন করে। তাই যদি আমরা সর্বাধিক ক্ষমতার ওজন নিতে পারি, এবং আনুপাতিক মানের সাথে একটি আইটেমের ওজনের একটি ভগ্নাংশ নিতে পারি, তাহলে আমাদের সর্বাধিক পরিমাণ মান খুঁজে বের করতে হবে যা আমরা পেতে পারি (নিকটতম পূর্ণসংখ্যাতে বৃত্তাকার)

সুতরাং, যদি ইনপুটটি ওজনের মত হয় =[6, 7, 3] মান =[110, 120, 2] ক্ষমতা =10, তাহলে আউটপুট হবে 178।

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

res :=0
- ওজন এবং মান সহ P জোড়ার একটি তালিকা তৈরি করুন এবং প্রতি ওজনের উপর ভিত্তি করে সাজান
- P-এ প্রতিটি জোড়ার জন্য করুন
  - cif ক্ষমতা 0, তারপর
    - লুপ থেকে বেরিয়ে আসুন
  - যদি জোড়া[0]> ক্ষমতা, তাহলে
    - res :=res + (pair[1] /(pair[0] / capacity) এর ভাগফল
    - ক্ষমতা:=0
  - অন্যথায় যখন জোড়া[0] <=ক্ষমতা, তারপর
    - res :=res + pair[1]
    - ক্ষমতা :=ক্ষমতা - জোড়া[0]
- রিটার্ন ফ্লোর মান ress

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

উদাহরণ

class Solution:
   def solve(self, weights, values, capacity):
      res = 0
      for pair in sorted(zip(weights, values), key=lambda x: - x[1]/x[0]):
         if not bool(capacity):
            break
         if pair[0] > capacity:
            res += int(pair[1] / (pair[0] / capacity))
            capacity = 0
         elif pair[0] <= capacity:
            res += pair[1]
            capacity -= pair[0]
      return int(res)

ob = Solution()
weights = [6, 7, 3]
values = [110, 120, 2]
capacity = 10
print(ob.solve(weights, values, capacity))

ইনপুট

[6, 7, 3],[110, 120, 2],10