01 가방 문제 설명

01 가방 문제 설명
1. 01 가방
1.1 문제
N 개의 아 이 템 과 V 용량 의 가방 이 있 습 니 다.제 i 아 이 템 을 넣 어 공간 을 차지 하 는 크기 Ci, 가 치 는 Wi 입 니 다.어떤 물건 을 가방 에 넣 으 면 가 치 를 총화 할 수 있 는 지 알 아 보 세 요.
1.2 기본 적 인 사고방식
이것 은 가장 기본 적 인 가방 문제 로 모든 아 이 템 이 하나 밖 에 없 으 므 로 놓 거나 놓 지 않 는 것 을 선택 할 수 있 는 것 이 특징 이다.하위 문제 로 상 태 를 정의 합 니 다. 즉 F[i,j] 앞의 i 개 아 이 템 을 j 용량 의 가방 에 넣 으 면 얻 을 수 있 는 최대 가 치 를 표시 합 니 다.그러면 그 상태 이동 방정식 은 F[i,j]=max{ F[i-1,j], F[i-1,j-Ci]+Wi} 이 방정식 은 앞의 i 개 아 이 템 을 선택 하면 용량 이 j 인 가방 에 넣 는 최대 가치 가 2 가지 경우 에 만 해당 하 며, i 개 상품 을 넣 거나 가방 에 넣 지 않 는 다 는 뜻 이다.i 번 째 상품 을 넣 지 않 으 면 문제 i - 1 번 상품 을 j 로 넣 는 가치 와 같 습 니 다. i 번 째 상품 을 넣 으 면 문제 i - 1 번 상품 을 넣 는 용량 이 j - ci 인 가치 에 그 자체 의 가 치 를 더 하 는 것 과 같 습 니 다.
따라서 이 상태 방정식 을 바탕 으로 다음 과 같은 코드 로 쓸 수 있 습 니 다.

// :c[i]   i          ,w[i]   i      

//          F[i,j]，      i        j      
var F = [];
for (var i = 0; i < =N; i++) {
  F[i] = [];
}

// 0   ，    ，     0
for (var j = 0; j <= V; j++) {
  F[0][j] = 0;
}

//   i     i   
for (var i = 1; i <= N; i++) {
  //   ，         j  
  for (var j = c[i]; j <= V; j++) {
    F[i][j] = Math.max(F[i - 1][j], F[i - 1][j - c[i] + w[i]]); //    
  }
}

1.3 공간 복잡 도 최적화
위의 방법 은 시간 과 공간의 복잡 도가 모두 O (VN) 이다.시간 복잡 도 는 더 이상 최적화 할 수 없다.공간 복잡 도 는 O (V) 까지 최적화 할 수 있다.가방 용량 이 j 일 때 대응 하 는 최대 값 을 V 크기 의 F 배열 로 저장 하 는 것 이다.
현재 의 문 제 는 i 의 공간 을 어떻게 없 애 는 지, 즉 i 번 째 상품 을 선택 할 때 내부 순환 이 끝나 면 F[j] 이 원래 의 F[i][j] 임 을 확인 할 수 있 습 니 다.즉:

// 
F[i][j] = Math.max(F[i - 1][j], F[i - 1][j - c[i] + w[i]]); //    (1)
//  
F[j] = Math.max(F[j], F[j - c[i] + w[i]]); //    (2)

내부 순환 의 의 미 는 i 개 아 이 템 을 가 져 오 는 데 있어 가방 용량 이 0 에서 V 까지 최대 가 치 를 얻 을 수 있다 는 것 이다.상태 방정식 (1) 에서 i 차 순환 은 i - 1 시의 F 결과 만 사용 하기 때문에 i 를 제거 하 는 것 이 합 리 적 입 니 다. i 차 순환 시 F 배열 은 이미 i - 1 시의 결과 이기 때 문 입 니 다.현재 주목 해 야 할 것 은 F[j] = Math.max(F[j], F[j - c[i] + w[i]]) 이 배열 이다. j 가 c [i] 에서 V 까지 의 과정 에서 우 리 는 등식 오른쪽 F 배열 을 확보 해 야 한다. 반드시 지난 번 에 계 산 된 값 이 어야 한다.만약 에 순환 변수 j 가 c[i] 에서 V 까지 의 순서 가 점점 증가한다 면 F[j-c[i]] 은 이 계산 후의 F 의 값 을 사용 하 는 것 이 틀림없다. 그러면 그렇지 않다.따라서 순환 순 서 를 V 에서 c [i] 로 줄 여야 합 니 다. 이 때 는 매번 사용 하 는 F 배열 을 확보 할 수 있 습 니 다.즉:

//   i     i   
for (var i = 1; i < =N; i++) {
  //   ，         j  
  for (var j = V; j >= c[i]; j--) {
    F[j] = Math.max(F[j], F[j - c[i] + w[i]]); //    
  }
}

1.4 세부 문제 초기 화
가방 문 제 를 풀 때 는 사실상 두 가지 다른 질문 이 있다.어떤 문 제 는 '마침 가방 을 가득 채 워 라' 는 최 적 화 를 요구 하고, 어떤 문 제 는 반드시 가방 을 가득 채 워 야 한다 고 요구 하지 않 았 다.첫 번 째 질문 법 은 가방 을 꼭 채 워 야 한다 고 요구 하면 초기 화 할 때 f[0] 를 제외 하고 다른 f[1...V] 는 모두 -Number.NEGATIVE_INFINITY 두 번 째 질문 법 으로 등 을 가득 채 워 야 한 다 는 요구 가 없 었 다. 다만 가격 이 최대한 비 싸 기 를 바 랄 뿐 초기 화 할 때 F[0...V] 를 모두 0 으로 설정 해 야 한다.
마침 가방 을 가득 채 워 가방 용량 이 0 일 때 만 0 으로 확인 할 수 있 고, 다른 크기 로 는 가 치 를 알 수 없 기 때문이다.가방 을 가득 채 우 는 것 을 요구 하지 않 고 가격 이 최대한 비 싸 기 를 바 랄 뿐 초기 값 은 0 이 될 수 있 으 며 포장 하지 않 는 다 는 것 도 해 입 니 다.
1.5 상수 최적화
내부 순환 에 대해 서 는 순환 하한 선 을 개선 할 수 있다.의미 에서 볼 때 내부 순환 j 는 공간 이 c[i] 에서 용량 V 까지 의 j 용량 크기, 즉 최소 가방 이 c [i] 크기 보다 큰 물건 이 어야 의미 가 있 지만 연락 외 순환 을 통 해 제 i 아 이 템, 즉 i ~ N 사이 의 아 이 템 은 넣 지 않 을 것 임 을 나타 낸다.그러면 이 물건 들 의 공간 을 구 한 다음 에 가방 용량 으로 넣 지 않 은 것 을 빼 면 한 계 를 얻 을 수 있다 bound=V-sum{w[i]...w[n]}. 이때 bound 와 c [i] 가 큰 사람 이 순환 의 하한 선 이다.

//   i     i   
for (var i = 1; i <= N; i++) {
  //   ，         j  
    var bound=Math.max(V-sum(c[i]...c[n]),c[i]);
  for (var j = V; j >= bound; j--) {
    F[j] = Math.max(F[j], F[j - c[i] + w[i]]); //    
  }
}

참고

가방 문제 9 강 2.0 베타 1.2 최 첨 익

가방 9 강 - 전편 상세 이해 와 코드 실현