ディスカバリーメソッド

発見法は最適数を厳密に探すよりも良い数を探すことに重点を置く方法である.二次的な戦略と言える.発見法では,貪欲法(greedy approach)がよく用いられる.貪欲法は選択の瞬間ごとに最善の選択をすることだ.最適な選択はプログラマーが決定します.
一つの問題を例に挙げましょう.泥棒は私の家に隠れて盗みをしようとした.しかし、窃盗犯のリュックサックには重さが限られており、家にいる時間が短いほど捕まえられる確率は小さくなる.窃盗犯はリュックサックに何を入れたらいいですか?
これはNP‐完全問題であり,最適解が要求される場合,時間複雑度はO(2^n)である.しかし、窃盗犯は最善の解を求める時間がない.そのため、自分の基準に基づいて、タイムリーに最適な選択をしなければならない.選択の基準が価値であれば、最も価値のあるものから始めてもいいです.そうではありません.重量の価値でやれば、重量が一番高いものを入れるだけでいいです.簡単に価値順に問題を処理し、JavaScriptを使用して問題を解決しましょう.

function greedyKnapsack(items, maxWeight){                  //items는 훔칠 수 있는 물건들의 이름, 가치, 무게를 배열로 저장한 것들을 요소로 갖는 배열, maxWeight는 가방의 무게제한
    let bagWeight=0;
    let bagItems=[];

    items.sort((before,after)=>(after[1]-before[1]));       //items를 가치순으로 내림차순으로 배열했다.
    for(let item of items){                                 //items의 item들을 0번째 인덱스부터 무게제한에 걸리지 않을 만큼 bagItems에 push합니다.
        if(bagWeight+item[2]<=maxWeight){
            bagWeight=bagWeight+item[2]
            bagItems.push(item.slice());
        }else{
            break;
        }
    }
    return bagItems;                                        //bagItems를 리턴합니다.
}

let fruits=[['apple',10,10],['banana',5,7],['orange',8,5]]; //간단한 test 코드입니다. 결과값은 apple, orange가 가방에 담긴것을 나타내는 배열입니다.
let maxWeight=19;

console.log(greedyKnapsack(fruits,maxWeight))

参考資料
1.本で描いたコンピューター科学路線図、著者:ブレストン・ペヘラ・ピル、著者:朴妍欧、p 72-76