ในบทความนี้ เราจะใช้ C++ ในการคำนวณจำนวนเส้นทาง W ของน้ำหนักในแผนผัง K-ary ในบทความนี้ เราได้ให้ต้นไม้ K-ary ซึ่งเป็นต้นไม้ที่แต่ละโหนดมีลูก K และแต่ละขอบมีน้ำหนักที่กำหนด โดยน้ำหนักจากมากไปน้อยจาก 1 ถึง K จากโหนดหนึ่งไปยังโหนดลูกทั้งหมด
เราจำเป็นต้องนับจำนวนเส้นทางสะสมที่เริ่มต้นจากรูทที่มีน้ำหนัก W และอย่างน้อยหนึ่งขอบที่มีน้ำหนักเท่ากับ M ดังนั้นนี่คือตัวอย่าง −
Input : W = 4, K = 3, M = 2 Output : 6
ในปัญหาที่กำหนด เราจะใช้ dp เพื่อลดความซับซ้อนของเวลาและพื้นที่ เมื่อใช้การจดบันทึก เราจะทำให้โปรแกรมของเราเร็วขึ้นมากและใช้งานได้สำหรับข้อจำกัดที่ใหญ่ขึ้น
แนวทาง
ในแนวทางนี้ เราจะสำรวจต้นไม้และติดตามขอบที่มีน้ำหนักอย่างน้อย 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) // if W becomes less than 0 then return 0
return 0;
if (W == 0) {
if (used) // if used is not zero then return 1
return 1; //as at least one edge of weight M is included
return 0;
}
if (DP[W][used] != -1) // if DP[W][used] is not -1 so that means it has been visited.
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); // if the condition is true
//then we will change used to 1.
else
answer += solve(DP, W - i, K, M, used);
}
return answer;
}
int main(){
int W = 3; // weight.
int K = 3; // the number of children a node has.
int M = 2; // we need to include an edge with weight at least 2.
int DP[W + 1][2]; // the DP array which will
memset(DP, -1, sizeof(DP)); // initializing the array with -1 value
cout << solve(DP, W, K, M, 0) << "\n";
return 0;
} ผลลัพธ์
3
คำอธิบายของโค้ดด้านบน
ในแนวทางนี้ การติดตามขอบของน้ำหนักใดๆ M จะรวมไว้อย่างน้อยหนึ่งครั้งหรือไม่ ประการที่สอง เราคำนวณน้ำหนักรวมของเส้นทางถ้ามันเท่ากับ W
เราเพิ่มคำตอบทีละหนึ่ง ทำเครื่องหมายเส้นทางนั้นว่าเยี่ยมชมแล้ว ดำเนินการต่อในเส้นทางที่เป็นไปได้ทั้งหมด และรวมอย่างน้อยหนึ่งขอบที่มีน้ำหนักมากกว่าหรือเท่ากับ M
บทสรุป
ในบทความนี้ เราแก้ปัญหาเพื่อค้นหาจำนวนพาธที่มีน้ำหนัก W ในทรี k-ary โดยใช้โปรแกรมไดนามิกใน O(W*K) ความซับซ้อนของเวลา
เรายังได้เรียนรู้โปรแกรม C++ สำหรับปัญหานี้และแนวทางที่สมบูรณ์ (Normal and excellent ) ซึ่งเราแก้ปัญหานี้ได้
