เพิ่มจำนวนเซ็กเมนต์ของความยาว p, q และ r ให้สูงสุดใน C++

คำชี้แจงปัญหา

เมื่อพิจารณาจากท่อนความยาว L ภารกิจคือการตัดท่อนไม้ในลักษณะที่จำนวนเซกเมนต์ทั้งหมดของความยาว p, q และ r เพิ่มขึ้นสูงสุด เซ็กเมนต์มีความยาวได้เฉพาะ p, q และ r

ถ้า l =15, p =2, q =3 และ r =5 เราก็สามารถสร้าง 7 เซ็กเมนต์ได้ดังนี้ −

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

อัลกอริทึม

เราสามารถแก้ปัญหานี้ได้โดยใช้โปรแกรมไดนามิก

<ก่อน>1. เริ่มต้นอาร์เรย์ dp[] ถึง 02 วนซ้ำจนถึงความยาวของแกน สำหรับทุกๆ 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 หากไม่สามารถทำการตัดที่ดัชนี i-th ans[l] จะให้จำนวนการตัดสูงสุดที่เป็นไปได้

ตัวอย่าง

#include ใช้เนมสเปซ std;int getMaximumSegments(int l, int p, int q, int r){ int dp[l + 1]; memset(dp, -1, sizeof(dp)); dp[0] =0; สำหรับ (int i =0; i <=l; ++i) { if (dp [i] ==-1) { ดำเนินการต่อ; } 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); } } ส่งคืน dp[l];}int main(){ int l =15, p =2, q =3, r =5; cout <<"จำนวนเซ็กเมนต์ =" < ผลลัพธ์
 
 เมื่อคุณคอมไพล์และรันโปรแกรมข้างต้น มันสร้างผลลัพธ์ดังต่อไปนี้−
 จำนวนเซ็กเมนต์ =7