โปรแกรม C++ หาเวลานานที่สุดไม่เกิน T ในการแก้โจทย์

คำอธิบายปัญหา

สมมติว่าเรามีอาร์เรย์ A N องค์ประกอบ และตัวเลข T พิจารณาอมลจะเข้าร่วมการแข่งขันเขียนโปรแกรม ระยะเวลา T นาที มีโจทย์ N ข้อ ใช้เวลา A[i] นาทีแก้ข้อ i เขาจะเลือกโจทย์ 0 ข้อขึ้นไป ให้เวลารวมไม่เกิน T ต้องการหาเวลานานที่สุดที่เป็นไปได้สำหรับชุดโจทย์ที่เลือก

ตัวอย่าง: T = 17; A = [2, 3, 5, 7, 11] ผลลัพธ์คือ 17 เพราะเลือก 4 ข้อแรก ใช้เวลา 2+3+5+7=17 นาที

ขั้นตอนการแก้ปัญหา

n := ขนาดของ A
กำหนดอาร์เรย์ b ขนาด n/2 และ c ขนาด n - n/2
สำหรับ i := 0 ถึง n/2-1: b[i] := A[i]
สำหรับ i := n/2 ถึง n-1: c[i-n/2] := A[i]
กำหนดอาร์เรย์ B, C
สำหรับ bit := 0 ถึง 2^(n/2)-1:
    p := 0
    สำหรับ i := 0 ถึง n/2-1:
        ถ้า bit AND 2^i ไม่เป็นศูนย์: p := p + b[i]
    ใส่ p ลง B
สำหรับ bit := 0 ถึง 2^(n-n/2)-1:
    p := 0
    สำหรับ i := 0 ถึง n-n/2-1:
        ถ้า bit AND 2^i ไม่เป็นศูนย์: p := p + c[i]
    ใส่ p ลง C
mx := 0
เรียงลำดับ C
สำหรับ i := 0 ถึง ขนาด B-1:
    ถ้า t - B[i] < 0: ข้าม
    itr = upper_bound(C, t - B[i])
    ลด itr ลง 1
    mx := max(mx, itr + B[i])
คืนค่า mx

ตัวอย่างโค้ด 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