โปรแกรม C++ หาคะแนนน้อยที่สุดที่ต้องทำเพื่อได้คะแนนรวม G

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

สมมติว่าเรามีอาร์เรย์ p และ c ทั้งคู่ D องค์ประกอบ และตัวเลข G ในการแข่งขันเขียนโปรแกรม แต่ละโจทย์มีคะแนนตามความยาก โจทย์ p[i] มีคะแนน 100*i p[1]+...+p[D] คือโจทย์ทั้งหมด ผู้ใช้มี total_score = base score + bonus

• Base score: ผลรวมคะแนนโจทย์ที่ทำได้
• Bonus: ทำครบทุกโจทย์คะแนน 100*i ได้โบนัส c[i] เพิ่ม

ตัวอย่าง: G = 500; P = [3, 5]; C = [500, 800] ผลลัพธ์คือ 3

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

D := ขนาดของ p
mi := 10000
สำหรับ i := 0 ถึง 2^D - 1:
    sum := 0, count := 0, at := 0
    อาร์เรย์เก็บ 10 บิต b เริ่มจากค่าบิตของ i
    สำหรับ j := 0 ถึง D-1:
        ถ้า บิตที่ j ใน b เป็น 1:
            count += p[j]
            sum += (j+1)*100*p[j] + c[j]
        มิฉะนั้น:
            at := j
    ถ้า sum < G:
        d := (G - sum + (at+1)*100 - 1) / ((at+1)*100)
        ถ้า d <= p[at]:
            sum += (at+1)*100*d
            count += d
    ถ้า sum >= G: mi := min(mi, count)
คืนค่า mi

ตัวอย่างโค้ด C++

#include <bits/stdc++.h>
using namespace std;

int solve(int G, vector<int> p, vector<int> c){
    int D = p.size();
    int mi = 10000;
    for (int i = 0; i < 1 << D; i++){
        int sum = 0;
        int count = 0;
        int at = 0;
        bitset<10> b(i);
        for (int j = 0; j < D; j++){
            if (b.test(j)){
                count += p.at(j);
                sum += (j + 1) * 100 * p.at(j) + c.at(j);
            } else {
                at = j;
            }
        }
        if (sum < G){
            int d = (G - sum + (at + 1) * 100 - 1) / ((at + 1) * 100);
            if (d <= p.at(at)){
                sum += (at + 1) * 100 * d;
                count += d;
            }
        }
        if (sum >= G) mi = min(mi, count);
    }
    return mi;
}

int main() {
    int G = 500;
    vector<int> P = { 3, 5 };
    vector<int> C = { 500, 800 };
    cout << solve(G, P, C) << endl;
}

อินพุต

500, { 3, 5 }, { 500, 800 }

เอาต์พุต

3