หาจำนวนเส้นทางที่มีน้ำหนัก W ใน K-ary Tree ด้วย C++

ในบทความนี้ เราจะใช้ C++ คำนวณจำนวนเส้นทางที่มีน้ำหนัก W ใน K-ary Tree เราได้รับ K-ary Tree ซึ่งเป็นต้นไม้ที่แต่ละโหนดมี K ลูก (children) และแต่ละขอบ (edge) มีน้ำหนัก (weight) กำหนดให้ โดยน้ำหนักจะเรียงลำดับจาก 1 ถึง K จากโหนดหนึ่งไปยังลูกทั้งหมดของมัน

เราต้องนับจำนวนเส้นทางสะสม (cumulative paths) เริ่มจากราก (root) ที่มีน้ำหนัก W และมีขอบอย่างน้อยหนึ่งขอบที่มีน้ำหนัก M ตัวอย่าง:

Input : W = 4, K = 3, M = 2 Output : 6

ในปัญหานี้ เราจะใช้ DP (Dynamic Programming) เพื่อลดความซับซ้อนด้านเวลาและพื้นที่ ด้วยการใช้ Memoization เราสามารถทำให้โปรแกรมเร็วขึ้นและใช้ได้กับข้อจำกัดขนาดใหญ่

วิธีการ (Approach)

ในวิธีนี้ เราจะเดินทางผ่านต้นไม้ (traverse the tree) และติดตามว่าขอบที่มีน้ำหนักอย่างน้อย M ถูกใช้หรือไม่ และน้ำหนักเท่ากับ W หรือไม่ หากใช่ เราจะเพิ่มคำตอบ

โค้ด

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

int solve(int DP[][2], int W, int K, int M, int used) {
    if (W < 0) // หาก W น้อยกว่า 0 คืนค่า 0
        return 0;
    if (W == 0) {
        if (used) // หาก used ไม่ใช่ศูนย์ คืนค่า 1
            return 1; // เพราะมีขอบน้ำหนักอย่างน้อย M อยู่แล้ว
        return 0;
    }
    if (DP[W][used] != -1) // หาก DP[W][used] ไม่ใช่ -1 หมายถึงเคยเยี่ยมชมแล้ว
        return DP[W][used];
    
    int answer = 0;
    for (int i = 1; i <= K; i++) {
        if (i >= M)
            answer += solve(DP, W - i, K, M, used | 1); // หากเงื่อนไขจริง จะเปลี่ยน used เป็น 1
        else
            answer += solve(DP, W - i, K, M, used);
    }
    return answer;
}

int main() {
    int W = 3; // น้ำหนัก
    int K = 3; // จำนวนลูกของโหนด
    int M = 2; // ต้องรวมขอบที่มีน้ำหนักอย่างน้อย 2
    int DP[W + 1][2]; // อาร์เรย์ DP
    memset(DP, -1, sizeof(DP)); // เริ่มต้นอาร์เรย์ด้วยค่า -1
    cout << solve(DP, W, K, M, 0) << "\n";
    return 0;
}

ผลลัพธ์

3

คำอธิบายโค้ด

ในวิธีนี้ เราติดตามว่ามีขอบที่มีน้ำหนัก M ถูกรวมอยู่อย่างน้อยหนึ่งครั้งหรือไม่ ส่วนที่สอง เราคำนวณน้ำหนักรวมของเส้นทาง หากเท่ากับ W เราเพิ่มคำตอบขึ้น 1 ทำเครื่องหมายเส้นทางนั้นว่าเยี่ยมชมแล้ว ดำเนินต่อผ่านเส้นทางที่เป็นไปได้ทั้งหมด และรวมขอบที่มีน้ำหนักมากกว่าหรือเท่ากับ M อย่างน้อยหนึ่งขอบ

สรุป

ในบทความนี้ เราแก้ปัญหาการหาจำนวนเส้นทางที่มีน้ำหนัก W ใน K-ary Tree โดยใช้ Dynamic Programming ด้วยความซับซ้อนด้านเวลา O(W × K)

เรายังเรียนรู้โปรแกรม C++ สำหรับปัญหานี้ และวิธีการแก้ปัญหาทั้งแบบปกติและแบบมีประสิทธิภาพ