เพิ่มจำนวน Segment ความยาว p, q, r ใน C++

โจทย์

ได้รับท่อนไม้ยาว L งานคือตัดท่อนไม้ให้จำนวน Segment ความยาว p, q, r มากที่สุด Segment ต้องมีความยาวเป็น p, q, หรือ r เท่านั้น

ถ้า l = 15, p = 2, q = 3, r = 5 สามารถทำได้ 7 Segment ดังนี้

{2, 2, 2, 2, 2, 2, 3}

อัลกอริทึม

ใช้ Dynamic Programming แก้ปัญหา

1. เริ่มต้น dp[] array เป็น 0
2. วนลูปจนถึงความยาวท่อนไม้ สำหรับทุก i ทำการตัด p, q, r ถ้าเป็นไปได้
3. อัปเดต ans[i+p] = max(ans[i+p], 1 + ans[i]), ans[i+q] = max(ans[i+q], 1 + ans[i]), ans[i+r] = max(ans[i+r], 1 + ans[i]) สำหรับทุกการตัดที่เป็นไปได้
4. ans[i] = 0 ถ้าตัดที่ Index i ไม่ได้ ans[l] จะให้จำนวนตัดสูงสุด

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

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

int getMaximumSegments(int l, int p, int q, int r) {
    int dp[l + 1];
    memset(dp, -1, sizeof(dp));
    dp[0] = 0;
    for (int i = 0; i <= l; ++i) {
        if (dp[i] == -1) continue;
        if (i + p <= l) dp[i + p] = max(dp[i + p], dp[i] + 1);
        if (i + q <= l) dp[i + q] = max(dp[i + q], dp[i] + 1);
        if (i + r <= l) dp[i + r] = max(dp[i + r], dp[i] + 1);
    }
    return dp[l];
}

int main() {
    int l = 15, p = 2, q = 3, r = 5;
    cout << "Number of segments = " << getMaximumSegments(l, p, q, r) << endl;
    return 0;
}

ผลลัพธ์

Number of segments = 7