จำนวนส่วนเส้นสูงสุดที่มีความยาว a, b, c ใน C++

ภาพรวมปัญหา

หาจำนวนส่วนเส้นสูงสุดที่มีความยาว a, b, c ที่สามารถสร้างได้จากจำนวนเต็มบวก N

ตัวอย่าง

Input: N = 8, a = 3, b = 1, c = 2
Output: 8
Explanation: ใช้ส่วนเส้นความยาว 1 จำนวน 8 ส่วน

Input: N = 13, a = 2, b = 7, c = 3
Output: 6

แนวทางแก้ปัญหา (Dynamic Programming)

• สร้างอาร์เรย์ MaxSeg[N+1] เก็บจำนวนส่วนสูงสุดสำหรับแต่ละความยาว
• เริ่มต้น MaxSeg[0] = 0, ที่เหลือ = -1
• สำหรับแต่ละ i จาก 0 ถึง N-1 ถ้า MaxSeg[i] != -1 อัปเดต MaxSeg[i+a], MaxSeg[i+b], MaxSeg[i+c]

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

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

int MaxSegment(int N, int a, int b, int c) {
    int MaxSeg[N + 1];
    memset(MaxSeg, -1, sizeof(MaxSeg));
    MaxSeg[0] = 0;
    
    for (int i = 0; i < N; i++) {
        if (MaxSeg[i] != -1) {
            if (i + a <= N) MaxSeg[i + a] = max(MaxSeg[i] + 1, MaxSeg[i + a]);
            if (i + b <= N) MaxSeg[i + b] = max(MaxSeg[i] + 1, MaxSeg[i + b]);
            if (i + c <= N) MaxSeg[i + c] = max(MaxSeg[i] + 1, MaxSeg[i + c]);
        }
    }
    return MaxSeg[N];
}

int main() {
    int N = 13, a = 2, b = 7, c = 3;
    cout << MaxSegment(N, a, b, c);
    return 0;
}

ผลลัพธ์

6