ค่าสูงสุดด้วยตัวเลือกหารหรือนำค่าเดิมใน C++

ในปัญหานี้ เราได้รับจำนวน N ภารกิจคือการสร้างโปรแกรมเพื่อหาค่าสูงสุดด้วยตัวเลือกที่จะหารหรือนำค่าเดิมใน C++

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

เพื่อหาค่าสูงสุด เราสามารถพิจารณาค่าใดค่าหนึ่งได้ สองทางเลือกคือ นำค่าเดิมมาใช้ หรือหารเพื่อหาค่าสูงสุด ค่าสามารถดึงมาได้จาก F(N/2) + F(N/3) + F(N/4) + F(N/5)

ตัวอย่างเพื่อเข้าใจปัญหา:

อินพุต: N = 8

เอาต์พุต: 9

คำอธิบาย

F(8) = F(8/2) + F(8/3) + F(8/4) + F(8/5) = F(4) + F(2) + F(2) + F(1) = 4 + 2 + 2 + 1 = 9

แนวทางแก้ปัญหา

แนวคิดคือเรียกฟังก์ชันซ้ำหลายครั้งสำหรับค่าการหาร เราใช้แนวคิด dynamic programming และสร้างอาร์เรย์เพื่อแก้ค่า F(i) จาก 0 ถึง N เพื่อนำกลับมาใช้ในการหาคำตอบ

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

#include <iostream>
using namespace std;

int calcMaximumValue(int N) {
    int F[N + 1];
    int divVal = 0;
    F[0] = 0;
    F[1] = 1;
    
    for (int i = 2; i <= N; i++) {
        divVal = (F[i / 2] + F[i / 3] + F[i / 4] + F[i / 5]);
        if (divVal > i)
            F[i] = divVal;
        else
            F[i] = i;
    }
    return F[N];
}

int main() {
    int N = 8;
    cout << "Maximum value with the choice of either dividing or considering as it is = " << calcMaximumValue(N);
    return 0;
}

ผลลัพธ์

Maximum value with the choice of either dividing or considering as it is = 9