บล๊อกนี้มีที่มาจากการที่ผู้เขียนไปอ่านกระทู้ เรื่องเล่าจาก MK สุกี้ 8คน 87บาท มา แล้วมาเห็นเพจ "วิทย์ เหี้ย เหี้ย" (ขออภัยที่ใช้คำไม่สุภาพ แต่มันเป็นเชื่อเพจเขา) แปะรูป นี้

https://www.facebook.com/photo.php?fbid=233819033451134

เห็นโจทย์ข้อนี้คำแรกที่คิดขึ้นมาคือ "Knapsack" หรือโจทย์ปัญหา (ทางโปรแกรมมิ่ง) เกี่ยวกับการรวมผลบวกของจำนวนหลายๆ จำนวนให้ได้ตามค่าที่กำหนด เช่นเรามี

1. ไข่ไก่ ราคาชุดละ 10 บาท
2. ผักบุ้ง ราคาชุดละ 17 บาท
3. วุ้นเส้น ราคาชุดละ 15 บาท

จะเขียนโปรแกรมยังไงให้รู้ว่าเราต้องใช้

ไข่ไก่ 1 ชุด +ผักบุ้ง 1 ชุด + วุ้นเส้น 4 ชุด

เพื่อจะให้ได้ราคารวมที่ต้องจ่าย 87 บาท

แนวคิด

เมื่อเรามีของหลายชิ้น แน่นอนว่ามันคิดยากโดยเฉพาะถ้าโจทย์ไม่ใช่เล่นจำนวนน้อยๆ แบบนี้เช่น

มี [12, 18, 34, 16, 2, 27] รวมให้ได้ 15467

แน่นอนว่าเราเริ่มจะมึนแล้ว

แล้วถ้าแบบนี้ล่ะ

มี [12] รวมให้ได้ 48

แน่นอนอีกล่ะว่าคิดง่ายมากเพราะเลขมันน้อย

ดังนั้นเมื่อเลขมันเยอะไป คิดไม่ได้เราจะใช้วิธีการที่เรียกว่า "divide and conquer" ในการคิดซึ่งเป็นหลักการของการเขียนโปรแกรมแบบ Recursion (ฟังก์ชั่นที่เรียกใช้ตัวเอง)

เริ่มด้วย [ 10 , 17 , 15 ] => 87

เริ่มจากการที่เราดึงเลขตัวแรกออกมาก่อน คือ 10

สมมุติมาก่อนว่าเราจะใช้ 10 x 1 ตัว = 10 ... แสดงว่าเราต้องการค่ารวมอีก 77 เหลือ [ 17 , 15 ]

ส่งคิดแบบเดียวกัน [ 17 , 15 ] => 77

เริ่มจากการที่เราดึงเลขตัวแรกออกมาก่อน คือ 17

สมมุติมาก่อนว่าเราจะใช้ 17 x 1 ตัว = 17 ... แสดงว่าเราต้องการค่ารวมอีก 60 เหลือ [ 15 ]

ส่งคิดแบบเดียวกัน [ 15 ] => 60

เอ๊ะ เหลือตัวเดียวแล้ว แบบนี้คิดได้ !

60 / 15 ได้ = 4 เศษ 0 --> ใช้ 15 x 4 ตัว

เขียนโค้ด

จากแนวคิดเราจะเห็นว่า function เราเมื่อได้ค่ามาคิดว่าคิด 2 อย่างนั่นคือ

ถ้าจำนวนเล็กพอที่จะคิดได้ (ในกรณีนี้คือ 1 ตัว) เราจะคิดคำตอบแล้ว return กลับไปเลย
ถ้าจำนวนที่ส่งมายังเยอะอยู่ (เยอะไปคิดไม่ได้!) เราจะดึงข้อมูลไว้ตัวนึงก่อน แล้วที่เหลือส่งต่อไปทำวิธีการแบบเดิม แต่ค่ารวมลดลง

ถ้าเอาไปเขียนเป็นโค้ดจะได้ประมาณนี้

function mk(n, total){

    if(items.length == 0) return false;

    var items = n.clone();
    var item = items.shift();

    if(items.length == 0){
            return total % item == 0 ? [total / item] : false;
    }
    else{
        var i, r;
        for( i=1; item * i <= total; i++ ){
            if( r = mk(items, total - item * i) ){
                return [i].concat(r);
            }
        }
    }

    return false;
}

var food = [10,17,15];
var price = 87

mk( food, price);

function เราจะรับ arrayของint และ ผลรวมที่ต้องการ เข้ามา

เข้ามาปุ๊บเราก็ดึงตัวแรกของ array ออกมาก่อนเป็น item และตัวที่เหลือเรียกว่า items

จากนั้นเช็กดูว่า items เหลือตัวเลขอีกมั้ย ถ้าไม่เหลือแสดงว่าตอนนี้มันเหลือ 1 ตัวแล้ว เล็กพอที่เราจะคิดได้ --> เช็กเลยว่ามันหารลงตัวหรือไม่ ถ้าหารลงตัว จำนวนที่ต้องใช้ก็จะเท่ากับ item / total เป็นคำตอบ

แต่ถ้าไม่ก็ return false แสดงให้เห็นว่าจำนวนที่ให้นี่น่ะ มันรวมยังไงก็ไม่ได้เท่ากับผลรวมที่ต้องการ

ถ้ารวมแรกเรารวมยังไงก็ไม่ได้ผลที่ต้องการ ครั้งที่ก็ก็ เอาตัวเลข item มาคูณ i เพิ่มขึ้นอีก แล้วยังเหลืออีกเท่าไหร่ก็ส่งไป recursion

ทำแบบนี้ไปเรื่อยๆ ถ้ามีขั้นหนึ่งที่มันรวมได้แล้ว มันก็จะส่งจำนวน (i) คือกลับมาว่าต้องใช้จำนวนเท่าๆ นะถึงจะรวมได้เป็นอันจบ

จำเป็นต้องใช้ให้ครบทุกตัวหรือเปล่า?

การหาว่าแต่ละค่าจะใช้ทั้งหมดกี่ตัวนั้นมันก็มี 2 กรณี คือต้องใช้อย่างน้อยค่าละ 1 ตัว หรือ ใช้ไม่ครบก็ได้ ขอแค่ค่ารวมได้กับที่ต้องการก็พอ

จากโค้ดข้างบนเราจะเห็นว่าเราจะมีการเรียกฟังก์ชั่นต่อทุกครั้งจนกว่าจะถึงตัวสุดท้าย (หมายความว่าเคสข้างบนน่ะ เป็นโค้ดสำหรับคิดแบบต้องใช้ทุกตัว)

ถ้าเราขอแค่ให้มันรวมให้ได้ค่าที่ต้องการก็พอล่ะ ?

เราก็แค่เพิ่มโค้ดให้มันเช็กก่อนว่าแค่ตัวมันตอนนี้เพียงพอมั้ยที่จะทำให้ได้ผลรวมที่ต้องการ

function mk(n, total){

    if(items.length == 0) return false;

    var items = n.clone();
    var item = items.shift();

    if(items.length == 0){
        return total % item == 0 ? [total / item] : false;
    }
    else{
        var i, r;
        for( i=1; item * i <= total; i++ ){
            if( total % (item * i) == 0 ){
                r = new Array(items.length);
                r[0] = i;
                return r;
            }
            else if( r = mk(items, total - item * i) ){
                return [i].concat(r);
            }
        }
    }

    return false;
}

var food = [10,17,15];
var price = 87

mk( food, price);