Knapsackアルゴリズム

Knapsackアルゴリズム
宝石のかばんを盗むという意味です

もういい.
いつ使いますか!!!
あくまで
家に帰っているのではなく、早く判断して・・・
(私もまだ知らないので、知ってから更新します)

アルゴリズムの原理

計算結果に基づいて値をパッケージに入れます.(リュック=並び)
結果を変えてまた結果を変える.
きおくげんり
このパターンを覚えて
bag[j] += bag[j - type[i]]

第一題

アンディに投獄中の恋人ジュリアを奪われ、怒ったジョージはブレッド、マットと一緒にアンディのカジノの地下の金庫を強奪することにした.様々な罠をくぐり抜けてついに金庫に入ったジョージと同行者たち.ジョージは刑務所で学んだアルゴリズムを利用してtargetの金額を盗む方法を計算し始めた.
たとえば、$50を盗むときに$10、$20、および$50がある場合は、以下の4つの方法で$50を盗むことができます.
50ドルを1枚盗む
20ドルを2枚、10ドルを1枚盗む
1枚$20、3枚$10を盗む
15ドル盗む
盗みたいtargetの金額と金庫のお金のタイプを入力し、ジョージがtargetを盗む方法の数を返します.

例

let output = ocean(50, [10, 20, 50]);
console.log(output); // 4

let output = ocean(100, [10, 20, 50]);
console.log(output); // 10

let output = ocean(30, [5, 6, 7]);
console.log(output); // 4

考えてみましょう。

カラーアルゴリズム(Knapsack Problem)

最初の解

function ocean(target, type) {
  // TODO: 여기에 코드를 작성합니다.
  // 출력값은 총 경우의 수
  // 타겟길이 만큼의 배열을 만든다. 
  //50, [10, 20, 50]);
  //훔치는 방법 배열
  let way = Array(target + 1).fill(0)
      way[0] = 1; //초기값 설정 
  for(let i = 0; i < type.length; i++){
    way[type[i]] += 1;
    for(let j = type[i] + 1; j <= target; j++ ){
      way[j] += way[j - type[i]]; 
    }
  }
  return way[target] 
}

第二の解釈

function ocean(target, type) {
  // 
  let bag = [1];

  
  for(let i = 1; i <= target; i++)
    bag[i] = 0;
  // 돈의 종류가 담겨있는 배열을 순차적으로 탐색   
  for(let i = 0; i < type.length; i++) {
  // target 금액까지 순차적으로 1씩 증가하면서    
    for(let j = 1; j <= target; j++)
  // bag의 인덱스가 type[i] 보다 큰 구간만
  // (작은 구간은 type[i]로 만들 수 없는 금액이기 때문에 탐색할 필요가 없다)    
      if(type[i] <= j)
  // 기존 경우의 수에 type[i]를 뺀 금액을 만들 수 있는 경우의 수를 더해준다       
        bag[j] += bag[j-type[i]];
  }
  // bag 의 target 인덱스에 target 금액을 훔칠 수 있는 경우의 수가 쌓이므로
  // 해당 값을 리턴해 준다
  return bag[target];
}

(苦悩の跡)

第二題

下図に示すように、複数単位の硬貨がある場合、最小の硬貨で小銭に両替します.
もしやるなら、どうすればいいですか.単位硬貨ごとに無限に使用できます.
■説明の入力
1行目はコインの種類数N(1<=N<=12)を与える.2行目にはN個の硬貨の種類が与えられ、2行目には探す金額M(1<=M<=500)が与えられる.
コインの種類は100元を超えない.
■出力説明
最初の行に探しているコインの最小個数を出力します.
■入力例
3
1 2 5
15
■出力例1
3
説明:5 5 5 5 5硬貨3個、探してもいいです.
上の問題と何が違いますか.
最初の問題は、ターゲットを見つけたすべての状況の数です.
2つ目の問題は目標の最小数です...

最初の解

  function solution(m, coin){  
     let answer=0;
     let dy=Array.from({length:m+1}, ()=>1000);
     dy[0]=0;
     for(let i=1; i<arr.length; i++){
        for(let j=coin[i]; j<=m; j++){
           dy[j]=Math.min(dy[j], dy[j-coin[i]]+1);
        }
     }
     answer=dy[m];
     return answer;
  }