ตัดก้าน

คันเบ็ดมีความยาว n นอกจากนี้ยังมีตารางอื่นซึ่งมีขนาดและราคาแตกต่างกันสำหรับแต่ละขนาด กำหนดราคาสูงสุดโดยการตัดแท่งและขายในตลาด

เพื่อให้ได้ราคาดีที่สุดโดยการตัดตำแหน่งต่างๆ และเปรียบเทียบราคาหลังตัดก้าน

ให้ f(n) คืนค่าสูงสุดที่เป็นไปได้หลังจากตัดแถวที่มีความยาว n เราสามารถเขียนฟังก์ชัน f(n) ได้ดังนี้

f(n) :=ค่าสูงสุดจากราคา[i]+f(n – i – 1) โดยที่ i อยู่ในช่วง 0 ถึง (n – 1)

อินพุตและเอาต์พุต

ป้อนข้อมูล :

ราคาความยาวต่างกันและความยาวของก้าน ความยาวเท่ากับ 8

ผลผลิต :

กำไรสูงสุดหลังการขายคือ 22.

ตัดแท่งยาว 2 และ 6 กำไรคือ 5 + 17 =22

อัลกอริทึม

rodCutting(price, n)

ป้อนข้อมูล: รายการราคา จำนวนราคาต่างๆ ในรายการ

ผลลัพธ์: กำไรสูงสุดโดยการตัดก้าน

Begin
   define profit array of size n + 1
   profit[0] := 0
   for i := 1 to n, do
      maxProfit := - ∞
      for j := 0 to i-1, do
         maxProfit := maximum of maxProfit and (price[j] + profit[i-j-1])
      done

      profit[i] := maxProfit
   done
   return maxProfit
End

ตัวอย่าง

#include <iostream>
using namespace std;

int max(int a, int b) {
   return (a > b)? a : b;
}

int rodCutting(int price[], int n) {    //from price and length of n, find max profit
   int profit[n+1];
   profit[0] = 0;
   int maxProfit;

   for (int i = 1; i<=n; i++) {
      maxProfit = INT_MIN;    //initially set as -ve infinity
      for (int j = 0; j < i; j++)
         maxProfit = max(maxProfit, price[j] + profit[i-j-1]);
      profit[i] = maxProfit;
   }
   return maxProfit;
}

int main() {
   int priceList[] = {1, 5, 8, 9, 10, 17, 17, 20};
   int rodLength = 8;
   cout << "Maximum Price: "<< rodCutting(priceList, rodLength);
}

ผลลัพธ์

Maximum Price: 22