ข้อถัดมา Price is wrong

จริงๆ ข้อนี้ไม่เกี่ยวอะไรกับราคา

เค้าจะให้ตัวเลขเรามาชุดนึง ซึ่งเป็นราคาสินค้า

แล้วให้ตอบว่าต้องแก้ตัวเลขอย่างน้อยกี่ตัวจึงทำให้ตัวเลขเรียงกัน

แต่แทนที่จะตอบตัวเลข เราต้องตอบชื่อสินค้าที่ราคาผิด

อ่านเพิ่มเติม ที่นี่



ข้อนี้ก็ยังเป็น Dynamic Programming

จุดสนุกของ Dynamic Programming คือ การวิเคราะห์หา subproblem

ซึ่งบางครั้ง ต้องอาศัยการคิดนอกกรอบแบบสุดๆ



วิธีคิดของข้อนี้คือ

ให้สมมติว่ามี ตัวเลขพิเศษมาประกบหัวท้าย เช่น

20 15 40 30 60

ให้เพิ่มตัวเลขน้อยสุด กับมากสุดเข้าไป เช่น เลข 0 และ 101 เป็น

0 20 15 40 30 60 101

แล้วลองหยิบตัวเลขมาตัวนึง เช่น 40

ทีนี้เราก็ได้ subproblem คือ เรียง 0 20 15 40 กับเรียง 40 30 60 100



ดังนั้น เราจะได้สูตรว่า



minGuess (min, max) = min { minGuess(min, i) + minGuess(i, max) }



แค่นี้เองครับ ง่ายบ่



ทีนี้ ตัวเลขที่เราจะเอามาเป็น node สำหรับแยก subproblem ต้องมีค่าระหว่าง min กับ max

เรามาสร้าง operator สำหรับทำ between กัน

let inline (<.) a b =
    a, b
let inline (.<) (a, b) c =
    a < b && b < c

มี 2 operators เหตุเพราะว่า f# ไม่รองรับการทำ ternary operator

ทีนี้วิธีใช้ operator นี้คือ a <. b .< c

ดูแล้วเข้าใจง่ายฝุดๆ



มาเริ่มกันเลยครับ

let solve names prices =
    let prices = Array.concat [[|0|]; prices; [|101|]]
    let priceOf = Array.get prices
    let nameOf n = Array.get names (n-1)

names คือ array ของชื่อสินค้า

prices คือ ราคาของสินค้า และทีนี้เรามีการประกบ 0 กับ 101 เข้าไปหัวท้าย

priceOf กับ nameOf คือการดึงราคาและชื่อ โดยใส่ index เข้าไป

let rec minGuess =
    let minGuessX (min, max) =
        let inside = { min+1..max-1 } |> Seq.filter (fun i -> priceOf min <. priceOf i .< priceOf max)
        if Seq.isEmpty inside then
            let newSet = { min+1..max-1 } |> Seq.map nameOf
                                          |> Set.ofSeq
            newSet.Count, newSet
        else
            seq {
                for i in inside do
                let leftCount,leftSet = minGuess (min, i)
                let rightCount,rightSet = minGuess (i, max)
                yield leftCount+rightCount, leftSet+rightSet
            } |> Seq.min
    memoize minGuessX

บรรทัด let inside คือ ดึงเฉพาะตัวเลขที่ราคาอยู่ระหว่าง min กับ max

ถ้าไม่เจอ inside หมายความว่าต้องปรับราคาทุกตัว

แต่ถ้าเจอ ก็ใช้ inside เป็น node แล้วหา minGuess ทั้งด้านซ้ายและด้านขวา

แล้ว return ผลเฉพาะค่า minimum



สุดท้ายก็ return ผล

let _,set = minGuess (0, prices.Length - 1)
String.Join(" ", set)

จบ