Knapsack 알고리즘

Knapsack 알고리즘은
보석을 훔치는 가방을 뜻하는걸로 유래....

됐고

언제 사용하느냐!!!!!!!
도대체

재귀가 아닌 빨리 판단해야함........
(나도 아직 몰라서 알게 되면 업데이트 하겠음)

알고리즘의 원리

계산한 결과값을 가방에 넣어 만든다.(가방 = 배열)
결과를 바꾸고 또 바꾸고

저장하는 원리임

이 패턴을 외우자

bag[j] += bag[j - type[i]]

1번 문제

자신이 감옥에 간 사이 연인이었던 줄리아를 앤디에게 빼앗겨 화가 난 조지는 브레드, 맷과 함께 앤디 소유의 카지노 지하에 있는 금고를 털기로 합니다. 온갖 트랩을 뚫고 드디어 금고에 진입한 조지와 일행들. 조지는 이와중에 감옥에서 틈틈이 공부한 알고리즘을 이용해 target 금액을 훔칠 수 있는 방법의 경우의 수를 계산하기 시작합니다.

예를 들어 $50 을 훔칠 때 $10, $20, $50 이 있다면 다음과 같이 4 가지 방법으로 $50을 훔칠 수 있습니다.

$50 한 장을 훔친다
$20 두 장, $10 한 장을 훔친다
$20 한 장, $10 세 장을 훔친다
$10 다섯 장을 훔친다
훔치고 싶은 target 금액과 금고에 있는 돈의 종류 type 을 입력받아, 조지가 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];
}

(치열하게 고민한 흔적)

2번문제

다음과 같이 여러 단위의 동전들이 주어져 있을때 거스름돈을 가장 적은 수의 동전으로 교환
해주려면 어떻게 주면 되는가? 각 단위의 동전은 무한정 쓸 수 있다.

▣ 입력설명
첫 번째 줄에는 동전의 종류개수 N(1<=N<=12)이 주어진다. 두 번째 줄에는 N개의 동전의 종류가 주어지고, 그 다음줄에 거슬러 줄 금액 M(1<=M<=500)이 주어진다.
각 동전의 종류는 100원을 넘지 않는다.

▣ 출력설명
첫 번째 줄에 거슬러 줄 동전의 최소개수를 출력한다.

▣ 입력예제
3
1 2 5
15
▣ 출력예제 1
3
설명 : 5 5 5 동전 3개로 거슬러 줄 수 있다.

위에 문제랑 어떤게 다른가?
1번 문제는 타겟의 모든 경우의 수를 찾는거고
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;
  }