C++ প্রোগ্রাম: T মিনিটের মধ্যে সমস্যা সমাধানের সর্বোচ্চ সম্ভাব্য সময় বের করা

মান লিখুন: আমাদের কাছে N উপাদান বিশিষ্ট একটি অ্যারে A এবং আরেকটি সংখ্যা T রয়েছে। আমল একটি প্রোগ্রামিং কনটেস্টে অংশ নিচ্ছে। কনটেস্টটি T মিনিট চলে এবং Nটি সমস্যা আছে। i-তম সমস্যা সমাধানে A[i] সময় লাগে। সে Nটি সমস্যার মাঝ থেকে শূন্য বা অধিক সমস্যা বেছে নেবে যাতে মোট সময় T মিনিটের চেয়ে বড় নয়। সমাধানের জন্য সর্বোচ্চ সম্ভাব্য সময় বের করতে হবে।

উদাহরণ

যদি ইনপুট হয় T = 17; A = [2, 3, 5, 7, 11], তবে আউটপুট হবে 17, কারণ প্রথম চারটি সমস্যা বেছে নিলে 2+3+5+7=17 মিনিট লাগে যা T-র চেয়ে বড় নয়।

সমাধানের ধাপসমূহ

n := A এর আকার
b অ্যারে (আকার n/2), c অ্যারে (আকার n-n/2)
for i := 0 থেকে n/2-1: b[i] := A[i]
for i := n/2 থেকে n-1: c[i-n/2] := A[i]

B, C অ্যারে তৈরি করুন
for bit := 0 থেকে 2^(n/2)-1:
    p := 0
    for i := 0 থেকে n/2-1:
        যদি bit & (1<

C++ বাস্তবায়ন
#include <bits/stdc++.h>
using namespace std;

int solve(int t, vector<int> A) {
    int n = A.size();
    vector<int> b(n / 2), c(n - n / 2);
    for (int i = 0; i < n / 2; i++) b[i] = A[i];
    for (int i = n / 2; i < n; i++) c[i - n / 2] = A[i];
    vector<int> B, C;
    for (int bit = 0; bit < (1 << (n / 2)); bit++) {
        int p = 0;
        for (int i = 0; i < n / 2; i++) {
            if (bit & (1 << i)) p += b[i];
        }
        B.push_back(p);
    }
    for (int bit = 0; bit < (1 << (n - n / 2)); bit++) {
        int p = 0;
        for (int i = 0; i < n - n / 2; i++) {
            if (bit & (1 << i)) p += c[i];
        }
        C.push_back(p);
    }
    int mx = 0;
    sort(C.begin(), C.end());
    for (int i = 0; i < B.size(); i++) {
        if (t - B[i] < 0) continue;
        auto itr = upper_bound(C.begin(), C.end(), t - B[i]);
        itr--;
        mx = max(mx, *itr + B[i]);
    }
    return mx;
}

int main() {
    int T = 17;
    vector<int> A = { 2, 3, 5, 7, 11 };
    cout << solve(T, A) << endl;
}

ইনপুট
17, { 2, 3, 5, 7, 11 }

আউটপুট
17