30/09/2018, 16:15
Giúp giải thích một đề bài tiếng anh - Cutting a Rod?
Dynamic Programming | Set 13 (Cutting a Rod)
Given a rod of length n inches and an array of prices that contains prices of all pieces of size smaller than n. Determine the maximum value obtainable by cutting up the rod and selling the pieces. For example, if length of the rod is 8 and the values of different pieces are given as following, then the maximum obtainable value is 22 (by cutting in two pieces of lengths 2 and 6)
length | 1 2 3 4 5 6 7 8
price | 1 5 8 9 10 17 17 20
And if the prices are as following, then the maximum obtainable value is 24 (by cutting in eight pieces of length 1)
length | 1 2 3 4 5 6 7 8
--------------------------------------------
price | 3 5 8 9 10 17 17 20
Tại ví dụ 1, cắt 2 phần độ dài 2 và 6 ra max price là 22 nghĩa là cắt như thế nào
Giải thích tương tự giúp em ở ví dụ 2 luôn
Được sử dụng tối đa bao nhiêu lần cắt
Bài liên quan
Tức là mình có một cái khúc cây dài bằng 8, thì nếu mình cắt ra thành hai đoạn dài
Thì tổng giá trị của cây này sẽ là 22, giá tốt nhất so với các cách cắt khác.
Ở ví dụ 2, nếu mình cắt ra làm 8 đoạn, mỗi đoạn 1 thì giá của nó sẽ là
Nghĩa là chỉ lấy ra được 1 khúc cây có độ dài bằng n inch bằng nhiều cách khác nhau sau cho giá trị của nó là lớn nhất. Vậy là tối đa cắt đc n lần khúc cây 1 hoặc ít nhất 1 lần khúc cây n.
Chính xác, bài này khá hay đấy. Em có giải pháp nào chưa?